What does Big O notation actually measure

Big O notation measures how the running time or memory consumption of an algorithm grows as the size of its input increases. It captures the dominant term of a function that describes the cost, ignoring lower‑order terms and constant factors. The result is an asymptotic upper bound that lets you compare algorithms independent of hardware or implementation details.

Why constants and lower‑order terms are dropped

When the input size becomes very large, the impact of a constant multiplier such as 5 × n or a term like n + 3 fades compared with the leading term. Therefore analysts drop constants and any terms that grow more slowly than the dominant one. This simplification yields a clean classification like O(n) or O(log n).

Big O is defined formally using limits: a function f(n) is O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. This definition ensures that beyond some threshold, f never exceeds a constant multiple of g. It provides a rigorous way to prove growth classifications.

Common growth classes:

• O(1) – constant time, the algorithm does the same amount of work regardless of n.
• O(log n) – logarithmic time, each step reduces the problem size dramatically, like binary search.
• O(n) – linear time, work grows proportionally with n, e.g., scanning an array.
• O(n log n) – linearithmic time, typical for efficient sorting algorithms such as mergesort.
• O(n²) – quadratic time, work grows with the square of n, as in simple bubble sort.

Deriving Big O for a simple loop:

1. 1Identify the loop variable and its range; for i from 1 to n the loop runs n times.
2. 2Count the basic operations inside the loop body; assume each iteration does a constant amount c of work.
3. 3Multiply the per‑iteration cost by the number of iterations: total work = c·n, which simplifies to O(n).

Running time of a linear algorithm:

Consider linear search on an unsorted array of length n. The algorithm examines each element until it finds the target, performing at most n comparisons. If n = 1,000, the worst‑case cost is 1,000 operations, which we write as O(n) because the cost grows linearly with n, regardless of the exact 1,000 value. Even though the exact count depends on hardware, Big O tells you that doubling the input roughly doubles the work for a linear algorithm, while a quadratic algorithm would quadruple the work when n is doubled.