Asymptotic Notations and Definitions

When we say merge-sort runs in O(n log n) and bubble-sort in O(n^2), we are not describing exact step counts — we are describing how the running time grows as the input becomes large. Asymptotic notation is the formal language of that growth, and GATE CSE expects you to be fluent in all five symbols: Big-O, Big-Omega, Theta, little-o, and little-omega.

Definition: Asymptotic notation describes how a function f(n) — typically the running time or space of an algorithm — grows as n approaches infinity, ignoring constant factors and lower-order terms.

Why we ignore constants and low-order terms

Two algorithms with running times 5n^2 + 30n + 10 and 2n^2 + n + 7 behave essentially the same way for large n — both are dominated by the n^2 term. As n doubles, both quadruple. The constants 5, 2, 30 and 10 are tied to hardware, language, and compiler. The shape of growth — quadratic — is intrinsic to the algorithm. Asymptotic notation captures the shape and discards the rest.

Big-O: the upper bound

Definition: f(n) = O(g(n)) if there exist constants c > 0 and n_0 > 0 such that **0 <= f(n) <= c . g(n)** for all n >= n_0.

In plain English: beyond some point, f never grows faster than a constant multiple of g. Big-O is the worst-case asymptotic upper bound. Crucially, you only need one pair (c, n_0) to make the inequality work — you don't have to find the tightest constant; you just have to find some valid one.

Example: f(n) = 3n + 4. Is f(n) = O(n)? Choose c = 4 and n_0 = 4. For n >= 4, 3n + 4 <= 4n. Yes, f(n) = O(n).

A subtle point: f(n) = 3n + 4 is also O(n^2), O(n^3), O(2^n) and so on — Big-O is an upper bound, and any function that bounds n from above will trivially bound 3n + 4 too. In practice we always quote the tightest O bound we know.

Big-Omega: the lower bound

Definition: f(n) = Omega(g(n)) if there exist constants c > 0 and n_0 > 0 such that **0 <= c . g(n) <= f(n)** for all n >= n_0.

This is the mirror image. Beyond some point, f never grows slower than a constant multiple of g. Big-Omega is the best-case asymptotic lower bound. Again, you only need to demonstrate one valid (c, n_0).

Example: f(n) = n^2 + 3n. Is f(n) = Omega(n^2)? Choose c = 1 and n_0 = 0. For all n >= 0, n^2 + 3n >= n^2. Yes.

Theta: the tight bound

Definition: f(n) = Theta(g(n)) if and only if f(n) = O(g(n)) AND f(n) = Omega(g(n)).

Equivalently, there exist constants c_1, c_2 > 0 and n_0 > 0 such that **0 <= c_1 . g(n) <= f(n) <= c_2 . g(n)** for all n >= n_0. Theta says g is both an upper and a lower bound — so f and g grow at exactly the same rate, up to a constant factor.

Theta is the strongest of the three primary notations. When you say merge sort is Theta(n log n) you are stating that it never does substantially better and never does substantially worse than n log n work — not just on the worst case, but always (or for the specified case you are analysing).

little-o: the strict upper bound

Definition: f(n) = o(g(n)) if for every constant c > 0 there exists an n_0 > 0 such that **0 <= f(n) < c . g(n)** for all n >= n_0. Equivalently, lim (n to inf) f(n) / g(n) = 0.

Notice the dramatic change of quantifier: Big-O needs some c; little-o requires every c, no matter how small. This makes little-o the much stricter claim: f is not just bounded above by g, it is negligible compared with g. Saying f(n) = o(g(n)) is the formal version of "f grows strictly slower than g".

Example: f(n) = n is o(n^2). Compute lim n / n^2 = lim 1/n = 0. So yes, n = o(n^2). But n is not o(n) — n / n = 1, not 0.

little-omega: the strict lower bound

Definition: f(n) = omega(g(n)) if for every constant c > 0 there exists n_0 > 0 such that f(n) > c . g(n) for all n >= n_0. Equivalently, lim (n to inf) f(n) / g(n) = infinity.

little-omega is the mirror of little-o. It says f grows strictly faster than g. So n^2 = omega(n) — the limit n^2 / n = n tends to infinity.

The big symbol-by-symbol comparison

It helps to line up the five notations against the analogy from real numbers.

A worked example

Question: Let f(n) = 4n^2 + 100n + 7. Show that f(n) = Theta(n^2).

Solution:

Step 1: Upper bound (Big-O). For n >= 1, we have 100n <= 100 n^2 and 7 <= 7 n^2. So f(n) = 4n^2 + 100n + 7 <= 4n^2 + 100n^2 + 7n^2 = 111 n^2. Choose c_2 = 111 and n_0 = 1. So f(n) = O(n^2).

Step 2: Lower bound (Big-Omega). For all n >= 0, f(n) = 4n^2 + 100n + 7 >= 4n^2 (since the other terms are non-negative for n >= 0). Choose c_1 = 4 and n_0 = 0. So f(n) = Omega(n^2).

Step 3: Combining Step 1 and Step 2 with c_1 = 4, c_2 = 111, n_0 = 1, we have 4 n^2 <= f(n) <= 111 n^2 for all n >= 1. By definition, f(n) = Theta(n^2).

Conclusion: f(n) = 4n^2 + 100n + 7 is Theta(n^2).

Why it matters

GATE CSE's Algorithms section asks routinely: "Which of the following is true: f(n) = O(g(n)), Omega(g(n)), Theta(g(n))?" Mastering the definitions — particularly the quantifier difference between Big-O and little-o — is what lets you eliminate trap options under exam pressure. Beyond GATE, every published algorithm-analysis paper, every textbook (CLRS, Sedgewick, Kleinberg-Tardos), and every system design interview uses these notations as the lingua franca for talking about performance.

Real-world example

When Google announced PageRank, the early papers proudly described its core matrix-multiplication step as O(n + m) per iteration on a graph of n pages and m links. The point was not that "the time is exactly n + m" — it was that the algorithm scales linearly in the size of the graph. As the web grew from millions to billions of pages, that linear-scaling claim, expressed in Big-O, was the only way to talk meaningfully about feasibility. The same notation lets you compare your O(n log n) sort against your friend's O(n^2) sort and predict, without running them, who will win on a million-element dataset.

Common misconception

Wrong idea: "O is worst-case and Omega is best-case." This is a popular but inaccurate shortcut. O and Omega are bounds on a function — typically, that function is the worst-case running time T_worst(n). One can speak of O(g) and Omega(g) bounds on the worst-case time, on the best-case time, or on any other measure. It is the function being bounded that is "worst case" or "best case"; the bound itself is just an upper or lower bound on that function.

Second wrong idea: "Theta means the algorithm always takes exactly this long." No — Theta still ignores constant factors and lower-order terms. Theta(n^2) means the running time is bounded between c_1 n^2 and c_2 n^2 for large n; the actual count might be 5 n^2 + 17 n + 3.

Tying the notations together (the inequality chain)

If you find this confusing, remember the following chain. For any f, g with f(n) = o(g(n)):

• f(n) = o(g(n)) => f(n) = O(g(n)), but the reverse is not true.
• f(n) = omega(g(n)) => f(n) = Omega(g(n)), but the reverse is not true.
• f(n) = Theta(g(n)) iff f(n) = O(g(n)) AND f(n) = Omega(g(n)).
• f(n) = o(g(n)) iff g(n) = omega(f(n)).

These implications, plus the quantifier rules, answer almost every multiple-choice question on this topic.

The fastest way to compare two functions f and g is the limit L = lim(n->inf) f(n)/g(n).

• L = 0 => f = o(g), so also f = O(g) but NOT Theta(g).
• L = infinity => f = omega(g), so f = Omega(g) but NOT Theta(g).
• L = constant c (0 < c < inf) => f = Theta(g) (tight bound both ways).
  When the limit oscillates (e.g., f(n) = n^(1+sin n)), the limit test fails and you must reason directly from the definition. Use L'Hopital's rule or take logs for tricky ratios like (log n)^k vs n^e or n! vs 2^n. Remember Stirling: n! ~ sqrt(2.pi.n).(n/e)^n, which gives log(n!) = Theta(n log n).

Key facts examiners exploit:

1. f(n) = O(g(n)) does NOT imply g(n) = O(f(n)). O is not symmetric.
2. Theta IS an equivalence relation (reflexive, symmetric, transitive); O and Omega are only reflexive and transitive (partial orders).
3. 2^(2n) is NOT O(2^n): ratio = 2^n -> infinity. Constants in exponents matter!
4. log(n!) = Theta(n log n), not Theta(n).
5. n^0.001 grows FASTER than (log n)^1000 eventually — any positive power of n beats any power of log n.
6. max(f,g) = Theta(f+g) for nonnegative functions.
   Memory aid for ordering: 'constants < log n < n^c (c<1) < n < n log n < n^2 < n^c (c>1) < 2^n < 3^n < n! < n^n'.

Cover the answer, recall, then check. 12 GATE cards on the properties of asymptotic notation.

Q1. Limit rule: if lim(n→∞) f(n)/g(n) = c with 0 < c < ∞, what can you conclude?
A1. f(n) = Θ(g(n)) — they grow at the same rate up to a constant.

Q2. What do lim f/g = 0 and lim f/g = ∞ imply?
A2. 0 ⟹ f = o(g) (hence O and not Θ); ∞ ⟹ f = ω(g) (hence Ω and not Θ).

Q3. Is Θ an equivalence relation?
A3. Yes — reflexive (f = Θ(f)), symmetric (f = Θ(g) ⟺ g = Θ(f)), and transitive.

Q4. State transpose symmetry.
A4. f = O(g) ⟺ g = Ω(f). Similarly f = o(g) ⟺ g = ω(f).

Q5. Are O and Ω reflexive? Symmetric?
A5. Reflexive: yes, f = O(f) and f = Ω(f). Symmetric: NO.

Q6. Are o and ω reflexive?
A6. No — they are irreflexive: f ≠ o(f) and f ≠ ω(f) (a function is never strictly dominated by itself).

Q7. Does trichotomy hold for asymptotic comparison?
A7. No. Not every pair is comparable — e.g. f(n) = n^(1+sin n) and g(n) = n are incomparable because sin n oscillates.

Q8. Compare n^0.99 and n/log n.
A8. (n/log n)/n^0.99 = n^0.01/log n → ∞, so n/log n = ω(n^0.99); n/log n grows faster.

Q9. Does log base affect an asymptotic bound?
A9. No. log_a n = log_b n / log_b a differs by a constant, so all logs are Θ(log n).

Q10. Θ(f(n) + g(n)) simplifies to?
A10. Θ(max(f(n), g(n))) when both are non-negative — the faster-growing term dominates.

Q11. Common misconception about "tight" O-bounds.
A11. O(g) need not be tight: 2n = O(n²) is valid but loose. Only Θ asserts a tight bound; o(g) explicitly means NOT tight.

Q12. Is a·f(n) = Θ(f(n)) for constant a > 0?
A12. Yes — positive constant multiples do not change the asymptotic class (constants are absorbed).

Worked Example

Problem: Using the formal definition of Big-O, prove that 3n² + 5n + 2 = O(n²) by explicitly finding suitable constants c and n₀.

Solution:
By definition, f(n) = O(g(n)) means there exist positive constants c and n₀ such that
0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

Here f(n) = 3n² + 5n + 2 and g(n) = n². We must bound f(n) by a multiple of n².

For all n ≥ 1, each lower-order term is at most the corresponding power of n²:
5n ≤ 5n² (since n ≤ n² for n ≥ 1),
2 ≤ 2n² (since 1 ≤ n² for n ≥ 1).

Therefore:
3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n².

So the definition holds with c = 10 and n₀ = 1:
0 ≤ 3n² + 5n + 2 ≤ 10·n² for all n ≥ 1.

Answer: With c = 10 and n₀ = 1, 3n² + 5n + 2 ≤ 10n² for all n ≥ 1, proving 3n² + 5n + 2 = O(n²).