When we talk about algorithm efficiency, we are not measuring wall-clock time — we are measuring how the algorithm scales as input grows. Big-O notation gives us a precise language to express that scaling, independent of hardware or implementation language.
What Does O(n) Actually Mean?
The letter n represents the size of the input. O(n) means the runtime grows linearly with n. Double the input, roughly double the time. The notation describes an upper bound — the worst-case behaviour as n approaches infinity.
Constant factors are intentionally dropped. O(2n) and O(n) are both written as O(n) because at scale, that factor of 2 is irrelevant compared to, say, the difference between O(n) and O(n²).
# O(n) — linear search
# We look at each element once, so time grows linearly.
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i # found it
return -1 # not found
The Complexity Hierarchy
Listed from fastest-growing (most efficient) to slowest (least efficient) as n increases:
- O(1) — Constant: runtime is the same regardless of n. Example: array index access, hash table lookup.
- O(log n) — Logarithmic: each step halves the problem space. Example: binary search.
- O(n) — Linear: one pass through the data. Example: finding the max in an unsorted array.
- O(n log n) — Linearithmic: typical of efficient comparison-based sorts. Example: merge sort, heapsort.
- O(n²) — Quadratic: nested loops. Example: bubble sort, insertion sort on unsorted data.
- O(2ⁿ) — Exponential: doubles with each additional input element. Example: naive recursive Fibonacci.
# O(log n) — binary search
# Each iteration cuts the search space in half.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
Space Complexity
Big-O applies equally to memory. An in-place sorting algorithm like heapsort uses O(1) extra space — it rearranges elements within the original array. Merge sort, by contrast, allocates auxiliary arrays totalling O(n) space, which can matter on memory-constrained systems.
Best, Average, and Worst Case
Big-O typically describes the worst case. Quicksort, for instance, has a worst-case of O(n²) (when the pivot is always the smallest or largest element), but an average-case of O(n log n) — which is why it outperforms merge sort in practice despite the theoretically inferior worst case.
"Premature optimisation is the root of all evil — but knowing your complexities before you write a line of production code is not premature. It is engineering." — adapted from Donald Knuth
Understanding complexity fundamentals lets you make informed trade-offs when designing systems that must operate at scale. The goal is never the fastest algorithm in the abstract — it is the right algorithm for your actual constraints.