Big-O Notation

Analogy categoryAnalogies

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

python

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_first

Analysis

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?

Time and Space Complexity

Abstract Data Types

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#BigONotation#Big#Notation#Works#Example#StudyNotes#SkillVeris