Overview of Asymptotic Analysis

Overview of Asymptotic Analysis

"Asymptotic" means one specific thing: behaviour as n heads to infinity. Asymptotic analysis deliberately throws away constants and low-order terms to expose the growth class underneath. Other pages give you the mechanics — the ∃c,n0 definition on Big-O Notation, the class catalogue on Functions and Their Growth Rates. This page examines the abstraction itself: a cleaner limit-based way to establish a bound, exactly why discarding the low-order terms is legitimate, and the cases where that discarding quietly betrays you.

The limit definition — asymptotics without guessing constants

Picking a constant c and threshold n0 to prove a bound is fiddly. There is a mechanical alternative: take the ratio of the two functions and send n to infinity. For T(n) and a candidate f(n), look at L = limn→∞ T(n)/f(n):

• L = 0 → T grows strictly slower than f: written T ∈ o(f) (little-o).
• 0 < L < ∞ → same growth class: T ∈ Θ(f) — a tight bound.
• L = ∞ → T grows strictly faster: T ∈ ω(f) (little-omega).

The little-o/little-omega notations are the strict cousins of Big-O/Big-Omega (which allow equality). "n = o(n2)" says n is strictly below quadratic; "n2 = O(n2)" merely says it does not exceed it. The full side-by-side of O/Ω/Θ is on Comparing Asymptotic Notations.

Worked: for T(n) = 3n2 + 100n + 5000 against f(n) = n2: T/f = 3 + 100/n + 5000/n2 → 3 as n→∞. The limit is a finite non-zero constant, so T ∈ Θ(n2) — and the low-order terms vanished because (100n + 5000)/n2 → 0, i.e. they are o(n2). That is the whole justification for "drop them," made rigorous in one line.

When the abstraction leaks: constants and low-order terms you dropped

Asymptotics promise something about large n. Below the threshold where the dominant term takes over, the terms you discarded are not negligible — they are the cost. Take the same T(n) = 3n2 + 100n + 5000. When does the 3n2 term actually overtake the 100n + 5000 you threw away? Solve 3n2 = 100n + 5000: 3n2 − 100n − 5000 = 0 ⇒ n = (100 + √70000)/6 ≈ 60.8. So for every input below n ≈ 61, the "negligible" terms are the majority of the work (at n = 60, the linear-plus-constant part is 11,000 vs the quadratic's 10,800). The Θ(n2) label is a true statement about the tail that is actively misleading about the first 60 inputs.

The extreme case: galactic algorithms

Push "the constant is dropped" to its breaking point and you get galactic algorithms — algorithms with a genuinely better asymptotic class whose hidden constant is so vast that the crossover point exceeds any input that will ever exist. Matrix multiplication is the classic ladder:

• Naive triple loop — O(n3).
• Strassen — O(n2.807), a real improvement with a manageable constant; production libraries actually switch to it for large matrices (crossover typically at a few hundred to ~1000 rows).
• Coppersmith–Winograd and its successors — O(n~2.37), asymptotically the best known, yet never used: the constant is astronomically large, so naive or Strassen wins for every matrix that fits in memory, in the world.

The lesson, and the judgment: an asymptotic bound is a claim about n → ∞. If the crossover n where the better class overtakes lies beyond your real inputs, the better complexity is worthless in practice. Asymptotic superiority is necessary, not sufficient — you must also check the crossover is reachable, which is exactly the empirical question handled on Measuring Efficiency.

Pitfalls unique to the asymptotic abstraction

• little-o vs Big-O. o is strict (limit 0, grows genuinely slower); O allows equality. Saying n2 = o(n2) is false; n2 = O(n2) is true.
• Amortized ≠ worst case. A dynamic array push is O(n) on the rare doubling but O(1) amortized over a sequence — the asymptotic average per operation, which is the honest figure when you do many. Saying "O(1) amortized" unprompted signals real depth.
• "Asymptotically better" is not "faster." The galactic case is the proof: a lower exponent can lose on every real input.
• Assuming the limit always exists. For oscillating costs the ratio may not converge to a single L; then you bound with O/Ω separately rather than claiming Θ.

Key takeaways

• Asymptotic analysis studies behaviour as n → ∞; the limit test lim T(n)/f(n) classifies it: 0 → o, finite non-zero → Θ, ∞ → ω.
• Dropping low-order terms is justified because they are o(dominant) — but only in the tail: for 3n2+100n+5000 the dropped terms dominate until n ≈ 61.
• Galactic algorithms show the abstraction's limit: a better class with an unreachable crossover (Coppersmith–Winograd's O(n2.37)) is useless in practice.
• Keep little-o (strict) distinct from Big-O (≤), and know amortized is an asymptotic average, not a worst case.