Introduction
Big-O notation is the standard mathematical language for describing the upper bound of an algorithm's growth rate as input size n becomes large. It answers the question: 'In the worst case, how does the cost of this algorithm scale as n increases?' Big-O deliberately ignores constant factors and lower-order terms because, for large enough n, only the dominant term determines how an algorithm behaves. This makes Big-O a powerful tool for comparing algorithms independent of hardware, language, or small input sizes.
Cricket analogy: Big-O is like a scout rating a bowler's economy rate as the pitch gets flatter over a long tournament — it ignores one lucky over's fluke figures and focuses on how the average cost per over scales as matches pile up.
How It Works
Formally, a function f(n) is O(g(n)) if there exist positive constants c and n0 such that f(n) <= c * g(n) for all n >= n0. In practice, this means we drop constants and lower-order terms: an algorithm that performs 3n + 5 operations is simply O(n). The most common complexity classes, from fastest to slowest growth, are: O(1) constant time — the cost does not depend on n at all, such as accessing an array element by index. O(log n) logarithmic time — the cost grows very slowly because the problem size is repeatedly halved, such as binary search on a sorted array. O(n) linear time — the cost grows proportionally with n, such as scanning every element of a list once. O(n log n) linearithmic time — typical of efficient comparison-based sorting algorithms like merge sort and quicksort (average case), which divide the problem and then do linear work at each level. O(n^2) quadratic time — the cost grows with the square of n, typical of algorithms with nested loops over the same data, such as bubble sort. O(2^n) exponential time — the cost doubles with every additional input element, typical of naive recursive solutions that explore all subsets, such as the unoptimized recursive Fibonacci or brute-force subset generation.
Cricket analogy: O(1) is like checking the current score on the scoreboard instantly regardless of overs played; O(log n) is like a knockout tournament bracket that halves the field each round; O(n) is like reviewing every ball of an innings once; O(n log n) is like sorting all batsmen's final averages efficiently at season's end; O(n^2) is like comparing every pair of players' head-to-head stats with nested loops; O(2^n) is like listing every possible batting-order permutation for an 11-player squad.
Example
def constant_time(arr):
return arr[0] # O(1): always exactly one operation
def logarithmic_time(sorted_arr, target):
# O(log n): binary search halves the search space each step
low, high = 0, len(sorted_arr) - 1
while low <= high:
mid = (low + high) // 2
if sorted_arr[mid] == target:
return mid
elif sorted_arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
def linear_time(arr):
total = 0
for x in arr: # O(n): one pass over all elements
total += x
return total
def linearithmic_time(arr):
# O(n log n): Python's built-in sort is Timsort, a comparison sort
return sorted(arr)
def quadratic_time(arr):
pairs = []
for i in arr: # outer loop: n iterations
for j in arr: # inner loop: n iterations for each outer
pairs.append((i, j)) # O(n^2) total pairs generated
return pairs
def exponential_time(elements):
# O(2^n): generates every possible subset of 'elements'
if not elements:
return [[]]
first, rest = elements[0], elements[1:]
without_first = exponential_time(rest)
with_first = [[first] + subset for subset in without_first]
return without_first + with_firstAnalysis
Each function in the example represents a distinct, well-known complexity class. constant_time never depends on the array's length, so it is O(1). logarithmic_time discards half the remaining search space on every iteration, so the number of steps needed is proportional to log2(n) — doubling the input only adds one extra step. linear_time visits each of the n elements exactly once, giving O(n). linearithmic_time relies on a comparison sort, which provably requires at least n log n comparisons in the worst case for general inputs. quadratic_time nests a loop of size n inside another loop of size n, producing n * n = n^2 total operations, which is why nested loops over the same collection are a classic red flag for O(n^2) behavior. exponential_time generates the full power set of the input (2^n subsets), and its recursive structure doubles the amount of work with every additional element, exactly matching O(2^n) growth. Recognizing these patterns in code — single loops, halving loops, nested loops, and branching recursion — is the fastest way to estimate an algorithm's Big-O complexity without formal proof.
Cricket analogy: constant_time is like glancing at the current run rate, O(1) regardless of overs bowled; logarithmic_time is like a rain-affected DLS calculation that halves the target range each iteration; linear_time is like reviewing all 300 balls of an innings once, O(n); linearithmic_time is like sorting a season's batting averages, requiring n log n comparisons; quadratic_time is like a nested loop comparing every batsman against every bowler, O(n^2); exponential_time is like generating every possible batting-order permutation, doubling with each added player, O(2^n).
Key Takeaways
- Big-O describes the worst-case upper bound of growth, ignoring constants and lower-order terms.
- O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, and O(2^n) exponential are the essential classes to recognize.
- A single loop over n elements is typically O(n); nested loops over the same data are typically O(n^2).
- Halving the problem each step (like binary search) produces O(log n).
- Naive recursive algorithms that branch into multiple calls without memoization often produce O(2^n).
Practice what you learned
1. What is the time complexity of binary search on a sorted array of n elements?
2. A function contains two nested loops, each iterating n times over the same array, with constant-time work inside. What is its time complexity?
3. Why is 3n + 100 simplified to O(n) in Big-O notation?
4. Which of these algorithms is a classic example of O(2^n) exponential time?
5. What complexity class is typical of efficient comparison-based sorting algorithms like merge sort?
Was this page helpful?
You May Also Like
Time and Space Complexity
Learn how to measure the efficiency of algorithms in terms of running time and memory usage.
Sorting Algorithms Overview
A survey of classic sorting algorithms, their complexities, stability, and when to choose each one.
Binary Search
The classic O(log n) algorithm for finding a target in a sorted array using repeated halving, with correct boundary handling.
Searching Algorithms Comparison
Comparing linear search, binary search, and hash-based lookup across time complexity, prerequisites, and practical trade-offs.