How does Big-O notation describe algorithm scalability?
Big-O notation describes an asymptotic upper bound on an algorithm’s resource usage as its input grows. It is commonly used to express time complexity, but it can also describe space complexity; it does not inherently mean average-case performance.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Formal Bounds
Big-O, Big-Omega, and Big-Theta describe different relationships between a measured function f(n) and a comparison function g(n).
| Notation | Meaning | Formal condition |
|---|---|---|
| Big-O | Upper bound | f(n) ≤ c · g(n) for some constants c and n₀, when n ≥ n₀ |
| Big-Omega | Lower bound | f(n) ≥ c · g(n) under the same conditions |
| Big-Theta | Tight bound | Both an upper and lower bound hold |
For example, if an algorithm takes Θ(n) time, it is also technically in O(n²). Big-Theta is more informative because it identifies the tight bound.
Best, average, and worst cases are a separate classification:
-
Best case: fastest behavior for the most favorable input.
-
Average case: expected behavior over a defined input distribution.
-
Worst case: slowest behavior for any valid input.
For example, hash-table lookup is O(1) best and average case but O(n) worst case because of collisions.
Common Complexity Classes
Here, n is the number of input elements. Space is auxiliary space, excluding the original input unless stated otherwise.
| Class | Example | Time | Extra space |
|---|---|---|---|
O(1) |
Read the first element | O(1) |
O(1) |
O(log n) |
Binary search | O(log n) |
O(1) |
O(n) |
Sum all elements | O(n) |
O(1) |
O(n log n) |
Merge sort | O(n log n) |
O(n) |
O(n²) |
Examine every pair | O(n²) |
O(1) |
O(2ⁿ) |
Recursively make two equal-sized choices | O(2ⁿ) |
O(n) stack |
O(n!) |
Recursively count permutations | O(n!) |
O(n) stack |
Deriving a Bound
Analyze the number of operations as n increases:
-
Drop constants and lower-order terms:
3n + 20becomesΘ(n). -
Sequential steps add:
O(n)followed byO(n)isO(n). -
Nested loops multiply:
niterations containingniterations isO(n²). -
Recursion uses a recurrence: For
T(n) = 2T(n/2) + O(n), the result isΘ(n log n), which can also be derived with the Master Theorem.
Use Θ when claiming a tight bound; reserve Big-O when only an upper bound is needed.
Time, Space, and Amortization
-
Time complexity counts the operations performed by the algorithm.
-
Space complexity counts additional memory, including the recursion stack. State whether the input itself is counted.
-
Total space includes the input and any data structure that stores it.
-
Amortized complexity describes the average cost per operation over a sequence, not one arbitrary operation.
For example, appending to a dynamic array is O(n) in the worst case because resizing may copy every element. Across many appends, however, append is O(1) amortized because copying occurs only after enough elements have been added. The array uses O(n) total storage, and a resize may temporarily require O(n) additional space.
Common Pitfalls
-
Do not use
Oto mean “average case”; state the case explicitly. -
Do not assume
O(n)is tight whenΘ(n)is known. -
Include recursion-stack space in recursive algorithms.
-
Decide whether the input is included in the reported space.
-
Distinguish worst-case cost from amortized cost for operations such as dynamic-array append.
-
Explain assumptions, such as a sorted input for binary search.
-
Common follow-ups include analyzing recurrence relations, identifying dominant terms, and comparing an algorithm’s time and space trade-offs.