Big-O, Θ, Ω notation

When two computers argue about which sorting algorithm is faster, they agree to settle it by counting steps on an infinitely large input — that agreement is asymptotic analysis, and Big O is its language. Every serious programmer and every GATE question relies on this framework.

Definition: Asymptotic analysis describes an algorithm's resource cost (time or space) as a mathematical function of input size n, retaining only the dominant term and stripping away constant factors — because as n grows large, only the shape of the growth curve matters, not its vertical scale.

Why we ignore constants and small n

A sorting algorithm with runtime 100n steps on a slow machine versus 2n² steps on a fast one: which is "better"? For n = 50 the slow machine takes 5,000 steps; the fast one takes 5,000 steps too — a tie. But at n = 10,000 the slow machine takes one million steps and the fast one takes two hundred million. The algorithm with lower growth rate always wins eventually, so we compare growth rates, not absolute times. Constants only shift the crossover point; they don't change who wins the race.

Definition: Big O (upper bound) — f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. "f grows at most as fast as g."

Definition: Big Omega Ω (lower bound) — f(n) = Ω(g(n)) if f(n) ≥ c · g(n) eventually. "f grows at least as fast as g."

Definition: Big Theta Θ (tight bound) — f(n) = Θ(g(n)) if f is both O(g) and Ω(g). The exact growth rate — neither faster nor slower.

Definition: Small o — the ratio f(n)/g(n) → 0; f is strictly slower. Small ω — the ratio → ∞; f is strictly faster.

The growth rate ladder — memorise this order

O(1) < O(log log n) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Class	Name	Typical algorithm
O(1)	Constant	Hash-table lookup, array access
O(log n)	Logarithmic	Binary search, balanced BST ops
O(√n)	Root	Naive primality test up to √n
O(n)	Linear	Single array scan, linear search
O(n log n)	Linearithmic	Merge sort, heap sort, FFT
O(n²)	Quadratic	Bubble / insertion / selection sort
O(n³)	Cubic	Floyd-Warshall, naïve matrix multiply
O(2ⁿ)	Exponential	Brute-force TSP, all subsets
O(n!)	Factorial	All permutations, brute-force TSP

Algebra of O-notation

You need these rules to simplify complex expressions rapidly:

• Sum rule: O(f) + O(g) = O(max(f, g)). E.g., O(n²) + O(n) = O(n²).
• Product rule: O(f) × O(g) = O(f · g). E.g., two nested loops each O(n) → O(n²).
• Constants disappear: O(7n²) = O(n²).
• Lower-order terms absorbed: O(n² + n + 100) = O(n²).
• Log base is irrelevant: O(log₂ n) = O(log₁₀ n) because log base change is a constant factor.
• Exponential bases differ: O(2ⁿ) ≠ O(3ⁿ) — these are genuinely different growth curves.

Solving recurrences

Divide-and-conquer algorithms yield recurrences. Key ones and their closed forms:

Recurrence	Algorithm	Solution
T(n) = T(n−1) + 1	Recursive linear scan	O(n)
T(n) = T(n−1) + n	Insertion sort (worst)	O(n²)
T(n) = T(n/2) + 1	Binary search	O(log n)
T(n) = T(n/2) + n	Quickselect (avg)	O(n)
T(n) = 2T(n/2) + 1	(uncommon)	O(n)
T(n) = 2T(n/2) + n	Merge sort	O(n log n)
T(n) = 2T(n/2) + n log n	—	O(n log² n)
T(n) = 4T(n/2) + n	—	O(n²)
T(n) = 7T(n/2) + n²	Strassen matrix multiply	O(n^log₂ 7) ≈ O(n^2.807)

The Master Theorem (Case summary)

For T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a):

• f(n) grows slower → T(n) = Θ(n^(log_b a)).
• f(n) grows at the same rate → T(n) = Θ(n^(log_b a) · log n).
• f(n) grows faster (with regularity condition) → T(n) = Θ(f(n)).

Time vs space complexity — they differ

Quicksort: O(n log n) average time, but only O(log n) auxiliary space (recursion stack depth). Merge sort: O(n log n) time, O(n) space (needs the auxiliary array). Both are O(n log n) in time, but merge sort uses more memory — a real engineering trade-off.

Best, average, and worst case

Algorithm	Best	Average	Worst
Linear search	O(1)	O(n/2) = O(n)	O(n)
Binary search	O(1)	O(log n)	O(log n)
Bubble sort	O(n)	O(n²)	O(n²)
Insertion sort	O(n)	O(n²)	O(n²)
Quick sort	O(n log n)	O(n log n)	O(n²)
Merge sort	O(n log n)	O(n log n)	O(n log n)
Hash table (good)	O(1)	O(1)	O(n)

Quicksort's worst case occurs when the pivot is always the smallest or largest element (already-sorted input with naïve pivot selection); randomised pivoting makes the expected case O(n log n).

Amortised analysis — the hidden averaging

Some operations are occasionally expensive but rarely so. Amortised complexity spreads the cost over a sequence. A dynamic array (Python list, Java ArrayList) doubles when full: each resize costs O(n), but it happens so rarely that each of n appends costs O(1) on average — the total work for n appends is O(n), so amortised O(1) per append. This is also why list.append() in Python is O(1) amortised despite occasional O(n) resizes.

Real-world impact of growth class

For n = 10⁶ (one million records — a modest database):

Class	Approx operations	Practical?
O(log n)	~20	instant
O(n)	10⁶	< 1 second
O(n log n)	~2 × 10⁷	fast
O(n²)	10¹²	hours
O(2ⁿ)	10^300,000	impossible

Why it matters: Before writing a line of code, knowing the growth class tells an engineer whether an approach will scale to production data. Every system design interview and every GATE algorithm question fundamentally asks: "can you classify complexity and choose the right algorithm for the scale?"

Real-world example: When UPI processes hundreds of millions of transactions per day, searching for a bank account must be O(log n) or O(1) via hash tables — not O(n). The choice between a balanced BST index and a linear scan is literally the difference between instant payment confirmation and a 30-minute timeout.

Common misconception: "Big O is the exact running time." Wrong. Big O is only an upper bound. An O(n²) algorithm might sometimes run in O(n) for specific inputs. For the exact asymptotic rate, use Θ (Big Theta). Additionally, saying bubble sort is O(n²) does not mean it always takes exactly n² operations — it means the worst-case cost does not grow faster than n². The bound is loose unless paired with Ω.

Question: Is 2ⁿ = O(2^(n/2))?
Solution:
Step 1: Write the ratio: 2ⁿ / 2^(n/2) = 2^(n − n/2) = 2^(n/2).
Step 2: As n → ∞, 2^(n/2) → ∞, so 2ⁿ does not grow at most as fast as 2^(n/2).
Conclusion: No, 2ⁿ ≠ O(2^(n/2)). Unlike with log bases, exponential bases cannot be changed by a constant factor — they represent genuinely different growth rates.

Cover the answer, recall, then check. 12 GATE cards on asymptotic bounds.

Q1. Formal definition of f(n) = O(g(n)).
A1. ∃ constants c > 0 and n₀ ≥ 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. It is an asymptotic upper bound.

Q2. Formal definition of f(n) = Ω(g(n)).
A2. ∃ c > 0, n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀. Asymptotic lower bound.

Q3. Formal definition of f(n) = Θ(g(n)).
A3. ∃ c₁, c₂ > 0, n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. Tight bound: f = Θ(g) ⟺ f = O(g) AND f = Ω(g).

Q4. How do o (little-o) and ω (little-omega) differ from O and Ω?
A4. o/ω are strict: f = o(g) ⟺ lim f/g = 0; f = ω(g) ⟺ lim f/g = ∞. The bound holds for every c > 0, and f = o(g) means f is strictly dominated by g.

Q5. The "operator" analogy for the five notations.
A5. O ≈ "≤", Ω ≈ "≥", Θ ≈ "=", o ≈ "<", ω ≈ ">".

Q6. Give the tight bound for 2n² + 3n log n + 100.
A6. Θ(n²). Lower-order terms and constants are dropped.

Q7. Is n = O(n²)? Is n² = O(n)?
A7. n = O(n²) is TRUE. n² = O(n) is FALSE. O is only an upper bound, so the smaller function is O of the larger.

Q8. Standard growth ordering (slowest → fastest).
A8. 1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ.

Q9. What is Θ(log(n!))?
A9. Θ(n log n), by Stirling's approximation log(n!) = n log n − n + Θ(log n).

Q10. Transitivity and the sum rule.
A10. f = O(g), g = O(h) ⟹ f = O(h). And O(f) + O(g) = O(max(f, g)); f·O(g) chains multiplicatively.

Q11. Is 2^(2n) = O(2ⁿ)?
A11. No. 2^(2n) = 4ⁿ = (2ⁿ)², which is NOT bounded by any constant times 2ⁿ. The base matters for exponentials.

Q12. Does O-notation tell you the worst case?
A12. No — that is a common trap. O/Θ/Ω bound a function; a worst-case running time can itself be given a Θ bound. You can say "worst case is O(n²)" and "best case is Ω(n)" for the same algorithm.

Asymptotic notation is the language every Algorithms question is written in. Directly it fetches 1–2 marks (identify the tight bound, compare growth rates), and indirectly it underlies every complexity answer in sorting, graphs, DP and data structures. Getting the definitions exactly right — not the hand-wavy "≈" versions — is what separates a correct answer from a distractor in GATE.

The five notations

For functions of n (eventually positive):

Notation	Meaning	Definition	Analogy
O(g)	upper bound	0 ≤ f ≤ c·g for n ≥ n₀	≤
Ω(g)	lower bound	0 ≤ c·g ≤ f for n ≥ n₀	≥
Θ(g)	tight bound	c₁g ≤ f ≤ c₂g	=
o(g)	strict upper	lim f/g = 0	<
ω(g)	strict lower	lim f/g = ∞	>

Limit test: if lim(n→∞) f/g = c with 0 < c < ∞ then f = Θ(g); = 0 gives f = o(g) ⊂ O(g); = ∞ gives f = ω(g) ⊂ Ω(g).

Growth hierarchy (memorise cold): 1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ. Any exponential beats any polynomial; log(n!) = Θ(n log n).

Exam Tricks & Tips

• 🎯 Drop constants and lower-order terms — Θ(3n² + 7n + 9) = Θ(n²). Do this first, every time.
• 🎯 Use the limit test to settle "which grows faster": compute lim f/g. Apply L'Hôpital or take logs for exponentials/factorials.
• 🎯 Take logs to compare exponential vs polynomial forms — e.g. n^(log n) vs (log n)ⁿ: compare (log n)² vs n·log log n → the second wins.
• 🎯 O + O = max: O(f) + O(g) = O(max(f, g)); a sequential block is dominated by its costliest part.
• 🎯 Transpose symmetry: f = O(g) ⟺ g = Ω(f); Θ is symmetric, O and Ω are not.
• 🎯 log base is irrelevant inside Θ (change-of-base is a constant factor), but the base of an exponential is not: 2ⁿ ≠ Θ(4ⁿ).
• ❌ Common mistake: believing "O means worst case." O/Ω/Θ bound functions; case analysis is a separate axis. An algorithm can be O(n²) worst and Ω(n) best.

Expected exam pattern

Multiple-select "which of the following are TRUE" over statements like f = O(g), pairwise growth-rate ordering, or "is f = Θ(g)?" for tricky pairs (n^(1+sin n) vs n, n/log n vs n^0.99). Usually 1–2 marks, high-frequency, low-effort if definitions are solid.

Quick recap

O = ≤, Ω = ≥, Θ = =, o = <, ω = >. Drop constants and lower terms, use the limit test for comparisons, remember the growth hierarchy, and never conflate the notation with best/worst-case analysis.

Key formulas

• O(g): f(n) = O(g(n)) if ∃ c, n₀ with 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀ (upper bound).
• Ω(g): f(n) ≥ c·g(n) eventually (lower bound).
• Θ(g): f(n) is both O(g) and Ω(g) (tight bound): c₁g ≤ f ≤ c₂g.
• little-o: f = o(g) ⇔ lim f/g = 0; little-ω: lim f/g = ∞.
• Limit test: if lim f/g = c (0<c<∞) then f = Θ(g).
• Growth order: 1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ.
• Sum rule: O(f)+O(g) = O(max(f,g)); product rule: O(f)·O(g)=O(f·g).
• Polynomial of degree d is Θ(n^d); log_a n = Θ(log_b n) (base irrelevant).

Usage: use the limit test to compare two functions quickly instead of guessing constants.

Worked Example

Problem: (a) Arrange the following functions in increasing order of asymptotic growth: n², 2ⁿ, n·log n, √n, n!, log n. (b) State whether 2ⁿ = O(n!) is true.

Solution:
(a) Compare growth classes from slowest to fastest. Logarithms grow slower than any positive power of n; polynomials grow slower than exponentials; exponentials grow slower than factorials.

Order the given functions:
log n < √n < n·log n < n² < 2ⁿ < n!.
(√n = n^0.5 beats log n; n·log n sits just above n; n² is polynomial; 2ⁿ is exponential; n! dominates all.)

(b) Is 2ⁿ = O(n!)?
Compare term by term: n! = 1·2·3···n, while 2ⁿ = 2·2·2···2 (n factors). For every factor beyond the second, n! uses a value ≥ 2ⁿ's factor of 2. Formally, for n ≥ 4, n! ≥ 2ⁿ. So 2ⁿ ≤ n! eventually, hence 2ⁿ = O(n!). The statement is TRUE.

Answer: (a) log n < √n < n·log n < n² < 2ⁿ < n!; (b) True, 2ⁿ = O(n!).