Big O Notation Without the Mystery

Describe how an algorithm scales as input grows, without getting distracted by machine-specific timing.

By Rishipal Singh · · 5 min read

Compare how constant, logarithmic, linear, and quadratic work grow.
Visual guide: Compare how constant, logarithmic, linear, and quadratic work grow.

Two programs can solve the same problem but behave very differently as the input grows. Big O notation describes how an algorithm's resource use scales with input size, rather than promising a specific number of seconds.

Look at growth, not a stopwatch

Suppose an algorithm checks every item in a list of n items. Its work grows proportionally to n, written O(n). If it compares every pair, the work grows roughly with n², written O(n²). Repeatedly halving a search space leads to O(log n).

Big O focuses on the dominant growth as n becomes large. It drops constant factors: O(3n + 10) is O(n). This makes it useful for comparing scale, not small-input speed.

Time is not the only resource

An algorithm can trade memory for speed. For example, a hash map may use extra space to avoid repeatedly scanning a list. When analyzing space, state whether you mean total memory or additional memory that grows with the input.

Make the analysis useful

  • Define what n represents.
  • Count how work changes as that input grows.
  • Check loops, nested loops, recursion, and extra data structures.

Complexity analysis helps you spot scalability problems early. It is a model, not a replacement for measuring real programs on realistic data.

Practice: compare growth

For sufficiently large n, which usually requires fewer operations: an O(n) algorithm or an O(n²) algorithm?

Reveal the explanation

O(n) grows more slowly. When input doubles, linear work roughly doubles, while quadratic work roughly quadruples; constants and small inputs can still affect real measurements.