Asymptotic Notations

Asymptotic notation is the precise language for “how fast a function grows”. Three symbols carry the whole subject:

The three notations

• Big-O (upper bound): f(n) = O(g(n)) if constants c > 0, n₀ exist with f(n) ≤ c·g(n) for all n ≥ n₀. “f grows no faster than g.”
• Big-Omega (lower bound): f(n) = Ω(g(n)) if f(n) ≥ c·g(n) beyond some n₀. “f grows at least as fast as g.”
• Theta (tight bound): f(n) = Θ(g(n)) when both hold — f is sandwiched between c₁·g(n) and c₂·g(n). This is the notation that pins a growth rate exactly.

How to actually use the definitions

To show 3n² + 5n = O(n²): pick c = 4; for n ≥ 5, 3n² + 5n ≤ 4n². Done — one valid (c, n₀) pair is a complete proof. Exam questions that “look theoretical” are usually just asking you to produce or verify such a pair.

Facts exams test again and again

• O is not worst case and Ω is not best case — notations bound functions; cases pick which function you’re bounding. Merge sort’s best case is Θ(n log n); binary search’s worst case is Θ(log n).
• n = O(n²) is TRUE (upper bounds needn’t be tight) — but it’s a useless bound, and “tightest correct option” is what scoring keys reward.
• Transitivity holds for all three; symmetry only for Θ (f = Θ(g) ⇔ g = Θ(f)).
• Little-o / little-ω are the strict versions: f = o(g) means f grows strictly slower — 2n = o(n²) but 2n ≠ o(n).

Key takeaways

Memorise the three definitions verbatim — GATE asks them directly — and always answer with the tightest notation the options allow.