Purpose Express an algorithm's running time or required memory without the details of less significant terms and constant coefficients.

VariationsBig O, Big Θ (Theta), and Big Ω (Omega). Big O is the only one that will come up during your interview process.

How it Works Big O describes the upper bound (or worst-case) complexity of an algorithm, based on an input of size n. 

Examples O(1) for array indexing, O(n) for linear search, O(nlgn) for Quicksort

Key Info

• Quicksort, Mergesort, and Heapsort run in O(nlgn) time
• Most other sorting algorithms run in O(n²) time
• Binary Search runs in O(lgn) time
• Linear Search runs in O(n) time‍

Cheat Sheet

‍‍

Further Explanation