Asymptotic Notations — previous-year questions

Notation questions are free marks once the definitions are automatic. This set drills the forms they actually take in GATE and company tests.

The recurring question shapes

• True/false bound claims: “Is 2ⁿ⁺¹ = O(2ⁿ)?” (yes — the constant 2 absorbs it) vs. “Is 2²ⁿ = O(2ⁿ)?” (no — 2ⁿ is itself a factor, no constant covers it). This exact pair has appeared in GATE.
• Tightest bound: several options are technically correct upper bounds; only the Θ-tight one scores. Rank the standard growth ladder instantly: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!
• Definition application: given f and g, decide which of O / Ω / Θ / o hold. Take limits when unsure: lim f/g = 0 → f = o(g); a finite non-zero limit → Θ; ∞ → ω.
• Property checks: transitivity, reflexivity, symmetry — Θ is an equivalence relation; O and Ω are only reflexive + transitive.

Working rules that resolve most options fast

• Polynomials: degree decides everything; coefficients never do.
• Logarithm bases differ by constants → log₂ n = Θ(log₁₀ n); but exponent bases matter → 3ⁿ ≠ O(2ⁿ).
• log(n!) = Θ(n log n) — Stirling’s approximation, quoted constantly.
• Comparing n^log c vs c^log n style pairs: take log of both and compare.

Exam discipline

Substitute small values only to disprove a claim, never to prove one — asymptotics live beyond any finite table of values. Solve every question in the video cold before marking this lesson complete.