You will encounter these complexities in 99% of interview problems. Knowing their shapes and the code patterns that produce them is essential.
1. $O(1)$ — Constant Time
- Pattern: Direct index access, hash map lookup, stack push/pop.
- Example:
array[5]— it doesn't matter if the array has 10 or 10 million items; the CPU computes the memory address directly and retrieves the value in one step. - The best achievable complexity.
2. $O(\log N)$ — Logarithmic Time
- Pattern: Halving the search space at each step. Binary search, balanced BST operations.
- Example: Looking up a name in a sorted phone book. Open the middle — name comes after, so discard the first half. Repeat. Even with a billion entries, you find the name in ~30 steps.
- Excellent. Scales to enormous inputs.
3. $O(N)$ — Linear Time
- Pattern: A single loop over all elements. Reading every item once.
- Example: Finding the maximum value in an unsorted array. You must inspect every element at least once.
- Acceptable. Often the best possible for unsorted data.
4. $O(N \log N)$ — Linearithmic Time
- Pattern: Efficient sorting algorithms — Merge Sort, Heap Sort, Quick Sort (average case).
- Example: Merge Sort divides the array in half ($\log N$ levels) and merges each level in $O(N)$ work.
- The practical floor for comparison-based sorting. Very common in interviews.
5. $O(N^2)$ — Quadratic Time
- Pattern: A nested loop where both loops iterate over the input.
- Example: Bubble Sort — for every element, compare it to every other element.
- Acceptable only for small N (< ~1,000). A red flag for large inputs.
6. $O(2^N)$ — Exponential Time
- Pattern: Generating all subsets of a set, naive recursive Fibonacci.
- Example: Cracking a password by trying every combination. Adding one character doubles the work.
- Impractical for N > ~30. Usually signals a missing memoization or DP optimization.