Comparing Asymptotic Notations

Comparing Asymptotic Notations

You already know the three big letters: O (Big-O, an upper bound), Ω (Big-Omega, a lower bound), and Θ (Big-Theta, a tight bound). This lesson is about the next skill interviewers actually test: given two functions or two notations, which one grows faster, and are they in the same class or not. Confusing "my algorithm is O(n²)" with "my algorithm is Θ(n²)" is one of the most common ways candidates lose credibility. Comparing is the tool that keeps you honest.

1. The plain-language intuition

Asymptotic notation describes how a cost function behaves as the input n heads toward infinity. Constants and low-order terms wash out, so 3n2 + 100n + 5 and n2 are treated as the same growth. Comparing two functions means asking a single question: as n gets huge, does one eventually and permanently dwarf the other, or do they stay locked together within a constant factor?

Think of it as a race with no finish line. We do not care who leads at n = 5. We care who is ahead once n is large enough and stays ahead forever after. A function that starts behind but has a steeper curve always wins the asymptotic race.

2. Precise definitions and the ordering

Let f(n) and g(n) be non-negative. The three notations are sets of functions:

• f = O(g): there exist constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0. (g is an upper bound on f — f grows no faster.)
• f = Ω(g): there exist c > 0, n0 with f(n) ≥ c·g(n) for n ≥ n0. (g is a lower bound — f grows no slower.)
• f = Θ(g): both hold at once — f = O(g) and f = Ω(g). (Same growth, tight.)

A clean way to compare two functions is the limit test. Let L = limn→∞ f(n)/g(n):

• L = 0 → f grows strictly slower → f = O(g) but not Θ; equivalently f = o(g) (little-o).
• L = ∞ → f grows strictly faster → f = Ω(g) but not Θ; equivalently f = ω(g) (little-omega).
• 0 < L < ∞ → same class → f = Θ(g).

The standard ranking of common classes, slowest-growing first:

1 < log n < √n < n < n log n < n2 < n3 < 2n < n! < nn

3. Worked example: comparing two real cost functions

Suppose algorithm A costs f(n) = 100n + 500 and algorithm B costs g(n) = 2n2. Which is asymptotically better, and where do they cross?

Cross-over by counting: set the operation counts equal, 100n + 500 = 2n2. At n = 10: A = 1500, B = 200 → B wins. At n = 50: A = 5500, B = 5000 → B still wins, barely. At n = 55: A = 6000, B = 6050 → A overtakes. From n ≥ 55 onward, A is permanently cheaper and the gap only widens: at n = 1000, A = 100,500 while B = 2,000,000 — B costs ~20× more.

Limit test confirms it: lim f/g = lim (100n + 500)/(2n2) = 0, so f = o(g) — A is strictly lower order. The verdict is asymptotic: f = O(g), g = Ω(f), and they are not Θ of each other. The lesson interviewers want you to internalize: B's smaller constant (2 vs 100) buys it an early lead, but a lower growth class always wins eventually. Constants decide the cross-over point; the exponent decides the war.

4. Pitfalls and what an interviewer probes

• O is an upper bound, not "the" running time. Every algorithm that is Θ(n) is also O(n2) and O(2n) — all true, all loose. Interviewers ask "can you make that tighter?" to see if you reach for Θ. Saying Θ when you mean it signals rigor.
• Best / worst / average are separate axes from O/Ω/Θ. They are commonly conflated but orthogonal. Quicksort is Θ(n log n) average and Θ(n2) worst case. You can state a tight Θ bound for a specific case. "Ω = best case" is a myth — you can give an Ω bound on the worst case too.
• Bases of logs do not matter (log2n = log10n / log102, a constant factor), so we just write log n. But the base of an exponent matters hugely: 3n is not O(2n).
• n log n vs n: a frequent trap. lim (n log n)/n = lim log n = ∞, so n log n is strictly worse than linear — not the same class.
• Dropping the wrong term. In n2 + n log n the dominant term is n2; the sum is Θ(n²). Always keep the fastest-growing term only.

5. When comparison matters in practice + trade-offs

Asymptotics predict the future, not the present. For small or bounded n, constants and cache behavior dominate — which is exactly why real libraries pick the lower class only past a threshold:

• Sorting: introsort/Timsort fall back to insertion sort (Θ(n2)) for tiny sub-arrays (n < ~16) because its small constants beat Θ(n log n) merge/quicksort below the cross-over. The asymptotically "worse" algorithm is genuinely faster there.
• Neighbouring classes are worth a real jump: going from Θ(n2) to Θ(n log n) turns a 10,000-element task from ~10⁸ to ~10⁵ ops — a 1000× win at scale. From Θ(2n) to Θ(n2) is the difference between "never finishes" and "instant."
• Trade-off honesty: a hash table is Θ(1) average lookup but Θ(n) worst case; a balanced BST is Θ(log n) guaranteed. If worst-case latency matters (real-time systems), the "slower" average class is the right call. Comparing classes is only step one — comparing which case you actually face is step two.

Key takeaways

• Compare by growth, not by value at small n: use the limit L = lim f/g — 0 means f is smaller-order (O, o), ∞ means larger-order (Ω, ω), and a finite positive L means same class (Θ).
• Constants set the cross-over point; the growth class wins the war. A smaller constant only buys an early lead, as 100n+500 beating 2n2 only past n = 55 shows.
• O / Ω / Θ are bounds; best / worst / average are cases — two independent axes. Always reach for the tight Θ on a named case, and never claim Ω means "best case."
• In practice, prefer the lower class past the cross-over, but let the required case and constants decide below it — which is why fast sorts fall back to insertion sort for tiny inputs.