Asymptotic Notation

Asymptotic notation is a language for describing how the cost of an algorithm grows as its input gets larger. Instead of measuring an algorithm in seconds — which depends on the machine, the compiler and the mood of your operating system — we count the operations it performs as a function of the input size n, and then keep only the part of that function that matters when n becomes large.

"Asymptotic" means "as n approaches infinity". A function that costs 3n² + 5n + 7 operations and one that costs n² operations are treated as the same shape, because for large n they both curve upward like a parabola. That shape is what the notation captures, and it is the single most useful thing to know about an algorithm before you commit to writing it.

• Hardware and language differences cancel out.
  • The same algorithm in C and in Python differs by a constant factor, and that factor disappears in asymptotic notation.
• It answers the question that actually matters: what happens as the input grows?
  • An O(n log n) sort beats an O(n²) sort on large inputs no matter whose laptop runs it.
• It gives a common vocabulary.
  • Saying "this is O(n)" is precise, while "this is fast" is not.
• It lets you reject a design before you build it.
  • If a problem has a million inputs and your idea is quadratic, you know it is wrong on paper — no prototype required.

Every asymptotic bound starts life as an exact count and then gets simplified twice:

1. Start with the exact operation count.
   T(n) = 3n² + 5n + 7
2. Drop the lower-order terms — they grow slower and become irrelevant.
   T(n) ≈ 3n²
3. Drop the constant factor — it does not change the shape of the curve.
   T(n) = Θ(n²)

Both simplifications are safe for the same reason: for large enough n, the n² term dwarfs everything else, and multiplying by 3 does not change which curve is on top.

The claim that lower-order terms "stop mattering" is easy to assert and easy to verify. Here is T(n) = 3n² + 5n + 7 broken into its three parts:

At n = 10 the smaller terms still contribute a sixth of the total. By n = 10,000 they contribute less than a fiftieth of one percent. Since asymptotic analysis is about the behaviour as n keeps growing, keeping those terms would add precision that is already noise — and would make the answer depend on details no two machines agree on.

Big-O says an algorithm grows no faster than some function. It is the ceiling.

Read it as: you are allowed to scale g(n) by any constant c you like, and you are allowed to ignore all small inputs before some cutoff n₀. If after that point your scaled g(n) stays above f(n) forever, then f is O(g).

Because it is only a ceiling, an O(n) algorithm is technically also O(n²) and O(2ⁿ). Those statements are true but useless, so by convention we quote the tightest upper bound we can prove.

The definition asks you to produce two numbers: a constant c and a cutoff n₀. Producing them is easier than it looks, because you are allowed to be generous. To show that 3n² + 5n + 7 = O(n²):

1. Rewrite every term so it is measured against n².
   • For n ≥ 1 we know n ≤ n² and 1 ≤ n², so 5n ≤ 5n² and 7 ≤ 7n².
2. Add the inequalities together.
   • 3n² + 5n + 7 ≤ 3n² + 5n² + 7n² = 15n², for all n ≥ 1.
3. Read off the witnesses.
   • c = 15 and n₀ = 1 satisfy the definition, so 3n² + 5n + 7 = O(n²) is proved.

Note how crude the bound is — 15n² is five times larger than the function it bounds. That is fine. The definition never asks for the smallest possible c, only for some c that works, which is exactly why constant factors carry no information in the final answer.

Big-Ω is the mirror image: the algorithm grows at least as fast as the given function. It is the floor.

Ω is how we express the hardness of a problemrather than an algorithm. "Any comparison-based sort is Ω(n log n)" means no such algorithm can ever do better, which is why merge sort at O(n log n) is considered optimal. A lower bound on a problem is a much stronger and much harder result than an upper bound on one algorithm: it is a statement about every algorithm that could ever be written.

Θ is the strongest of the three: it holds when the same function is both an upper and a lower bound, so the growth rate is pinned exactly.

Equivalently: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). Merge sort is Θ(n log n) because it never does better and never does worse. Quick sort is not Θ(n log n) — its worst case is Θ(n²), so only a per-case statement is honest.

The lowercase forms are the strict versions. Big-O allows f and g to grow at the same rate; little-o does not.

• f(n) = o(g(n)) — f grows strictly slower than g. The bound must hold for every constant c, not just some c. Example: n = o(n²), but n is not o(n).
• f(n) = ω(g(n)) — f grows strictly faster than g. Example: n² = ω(n).

The difference between O and o is the difference between "there exists a c" and "for every c". Because n² = O(n²) but n² ≠ o(n²), the strict forms rule out the case where the two functions grow at the same rate.

The middle column is a useful mnemonic but not a perfect one. Unlike numbers, two functions need not be comparable at all — you can construct oscillating functions where neither is O of the other — so treat the ≤ / ≥ / = analogy as intuition rather than as a theorem.

These properties are what let you manipulate complexity expressions without going back to the definition each time:

• Transitivity — it holds for all five notations.
  • If f = O(g) and g = O(h), then f = O(h).
• Reflexivity — for O, Ω and Θ only.
  • f = O(f), f = Ω(f) and f = Θ(f) are always true. The strict forms are not reflexive: f is never o(f).
• Symmetry — Θ only.
  • If f = Θ(g), then g = Θ(f). O and Ω are not symmetric.
• Transpose symmetry — O and Ω are mirrors.
  • f = O(g) if and only if g = Ω(f). The same relationship links o and ω.
• The sum rule — the larger term absorbs the smaller.
  • O(f) + O(g) = O(max(f, g)). This is why sequential blocks of code collapse to whichever is slowest.
• The product rule — nested work multiplies.
  • O(f) × O(g) = O(f × g). This is why an O(log n) loop inside an O(n) loop is O(n log n).

When two functions are hard to compare by eye — is n log n bigger than n^1.5? — the limit test settles it mechanically. Evaluate the ratio as n approaches infinity:

For the example above, n log n divided by n^1.5 is log n / n^0.5, which tends to 0, so n log n = o(n^1.5) — the linearithmic function is the smaller of the two. This test is also the quickest way to confirm the standard ordering: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!.

Ordered from best to worst. The last column is roughly how many operations you perform at n = 1,000.

The jump from O(n log n) to O(n²) is where most interview problems live, and the jump from O(n²) to O(2ⁿ) is where problems stop being solvable by brute force at any realistic size.

In practice you rarely write a proof. You read the loop structure and apply the sum and product rules:

function analyse(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {   // O(n)
    sum += arr[i];
  }

  for (let i = 0; i < arr.length; i++) {   // O(n) x O(n)
    for (let j = 0; j < arr.length; j++) { //   = O(n^2)
      if (arr[i] === arr[j]) sum++;
    }
  }

  return sum;                              // O(1)
}
// Total: O(n) + O(n^2) + O(1) = O(n^2)

function analyseTwo(n) {
  let count = 0;
  for (let i = 1; i < n; i *= 2) {         // O(log n)
    for (let j = 0; j < n; j++) {          //   x O(n)
      count++;
    }
  }
  return count;                            // Total: O(n log n)
}

1. Constant factors are dropped.
   • O(3n) is written O(n); O(n/2) is also O(n).
2. Only the dominant term survives.
   • O(n² + n log n + 100) collapses to O(n²).
3. Sequential blocks add, so the larger one wins.
   • A loop of O(n) followed by a loop of O(n²) is O(n²).
4. Nested loops multiply.
   • An O(n) loop inside another O(n) loop is O(n²).
5. The base of a logarithm does not matter.
   • log₂n and log₁₀n differ by a constant factor, so both are written O(log n).
6. Different input sizes stay separate.
   • A loop over n nested in a loop over m is O(n · m) — collapsing it to O(n²) is only correct if n and m are the same quantity.

• Big-O is the default in engineering and interviews.
  • When someone asks "what is the complexity of your solution?", they expect a Big-O answer, and they expect it to be the tightest one you can justify.
• Big-Ω is how you talk about problems, not algorithms.
  • "Comparison sorting is Ω(n log n)" is a statement about every possible algorithm, and it is what makes merge sort provably optimal.
• Big-Θ is what textbooks use when the bound is exact.
  • Θ is the honest choice for algorithms whose cost does not depend on the input arrangement, like heap sort or a full array traversal.
• Little-o and little-ω appear mostly in proofs.
  • They are useful when you need to argue that one term becomes negligible compared to another, which is common when solving recurrences.

• Treating Big-O as "the worst case".
  • Notation and case are independent. You can state a Big-O bound on the best case, and a Big-Ω bound on the worst case.
• Writing O(2n) or O(n + 5).
  • Both are just O(n) — the point of the notation is to discard that detail.
• Using O where Θ is meant.
  • Every O(n) algorithm is also O(n²), because O is only an upper bound. Θ is the claim that the bound is tight.
• Reading the equals sign as equality.
  • f(n) = O(g(n)) really means "f belongs to the set O(g)". That is why you can write n = O(n²) but never O(n²) = n — the relation only runs one way.
• Forgetting that constants matter for small n.
  • An O(n log n) algorithm with a huge constant can lose to an O(n²) one on tiny inputs — which is why real sort implementations switch to insertion sort for short subarrays.
• Assuming a smaller notation always means a faster program.
  • Asymptotics compare growth, not speed at your actual input size. They tell you which algorithm wins eventually, not which wins today.

• Asymptotic notation describes growth as n → ∞, not speed at any particular size.
• O is an upper bound, Ω is a lower bound, Θ is both at once, and o and ω are their strict versions.
• A bound only has to hold past some cutoff n₀, and you may scale g(n) by any constant — which is why constants never survive.
• Always quote the tightest bound you can justify; a loose O is true but says nothing.
• The equals sign in f = O(g) means set membership, so the relation only reads left to right.
• The limit test decides any comparison you cannot make by eye.