GATE/Algorithms/Asymptotic Analysis & Complexity
Sign in to track
Medium18 min readAlgorithms

Asymptotic Analysis & Complexity

Asymptotic analysis measures algorithm efficiency by describing how running time grows with input size. It forms the foundation of every GATE Algorithms question.

Key Points

  • ·Big-O (O) — upper bound: f(n) = O(g(n)) if ∃ c, n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀
  • ·Omega (Ω) — lower bound; Theta (Θ) — tight bound (both upper and lower)
  • ·Common hierarchy: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
  • ·Master Theorem: T(n) = aT(n/b) + f(n) — compare f(n) with n^(log_b a)
  • ·Recursion tree: draw tree, sum cost per level × levels
  • ·Amortised analysis: average cost over a sequence of operations

Why Do We Need Complexity?

Imagine two students solving the same problem. Student A writes a program that takes 1 second for 100 items. Student B's program takes 0.001 seconds for 100 items — but 1000 seconds for 1000 items. Who wrote the better algorithm?

As the input grows, the growth rate matters far more than the constant factor. Big-O notation captures this growth rate.

Big-O, Omega, and Theta — The Three Notations

Think of them as: - O (Big-O): "at most this fast" — like a speed limit sign. Your algorithm is no slower than this. - Ω (Omega): "at least this slow" — the best case guarantee. - Θ (Theta): "exactly this rate" — both upper and lower bound match.

Formal definition of O: f(n) = O(g(n)) if there exist positive constants c and n₀ such that:

f(n) ≤ c · g(n)   for all n ≥ n₀

Example: Is 3n² + 5n + 10 = O(n²)?

Can we find c such that 3n² + 5n + 10 ≤ c·n² for large n?
3n² + 5n + 10 ≤ 3n² + 5n² + 10n²   (since n ≤ n², 1 ≤ n² for n≥1)
              = 18n²
Yes! 3n² + 5n + 10 = O(n²) with c=18, n₀=1.

The Complexity Hierarchy

O(1)        → constant       Lookup in hash table
O(log n)    → logarithmic    Binary search
O(√n)       → square root    Some number theory
O(n)        → linear         Single loop through array
O(n log n)  → linearithmic   Merge sort, heap sort
O(n²)       → quadratic      Nested loops, bubble sort
O(n³)       → cubic          Floyd-Warshall, matrix multiply
O(2ⁿ)       → exponential    Brute-force subsets
O(n!)       → factorial      All permutations

Visualising growth (approximate values for n=10):

log₂(10) ≈ 3        n = 10         n log n ≈ 33
n² = 100            2ⁿ = 1024      n! = 3628800

For n=100: n! has 158 digits. Exponential algorithms are impractical for large inputs.

Master Theorem — Solving Recurrences in 3 Steps

Many divide-and-conquer algorithms produce recurrences of the form:

T(n) = a·T(n/b) + f(n)

Where: - a = number of subproblems - b = factor by which input shrinks - f(n) = cost of dividing + combining

Step 1: Compute the "pivot" exponent: p = log_b(a)

Step 2: Compare f(n) with n^p

Step 3: Apply the matching case:

Case Condition Solution
Case 1 f(n) = O(n^(p−ε)) — combining is cheap T(n) = Θ(n^p)
Case 2 f(n) = Θ(n^p) — combining matches subproblems T(n) = Θ(n^p log n)
Case 3 f(n) = Ω(n^(p+ε)) — combining dominates T(n) = Θ(f(n))

Worked Examples

Merge sort: T(n) = 2T(n/2) + n

a=2, b=2, p = log₂(2) = 1
f(n) = n = Θ(n¹) = Θ(n^p)  → Case 2
T(n) = Θ(n log n)  ✓

Binary search: T(n) = T(n/2) + 1

a=1, b=2, p = log₂(1) = 0
f(n) = 1 = Θ(n⁰) = Θ(n^p)  → Case 2
T(n) = Θ(log n)  ✓

Strassen's matrix mult: T(n) = 7T(n/2) + n²

a=7, b=2, p = log₂(7) ≈ 2.807
f(n) = n² = O(n^(2.807−ε))  → Case 1
T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)

Recursion Tree Method

When Master Theorem doesn't apply (e.g., T(n) = T(n/2) + T(n/4) + n), draw the recursion tree.

T(n) = 2T(n/2) + n (merge sort):

Level 0:           n                  cost = n
Level 1:       n/2   n/2              cost = n
Level 2:     n/4 n/4 n/4 n/4          cost = n
...
Level log n:  1 1 1 ... (n leaves)    cost = n

Number of levels = log₂n (input halves each time)
Cost per level = n (consistent)
Total = n × log n = O(n log n)

Amortised Analysis

Sometimes individual operations are expensive, but when averaged over many operations, the cost per operation is cheap.

Dynamic array doubling: When array is full, allocate 2× space and copy all elements. This costs O(n) for that one push.

But how often does it happen?

Pushes:   1  2  3  4  5  6  7  8  9 ...
Cost:     1  1  2  1  4  1  1  8  1 ...
          ^     ^     ^           ^
          cheap copy(2) copy(4)  copy(8)

Total cost for n pushes = n + (1 + 2 + 4 + ... + n) = n + 2n = 3n = O(n) Amortised cost per push = 3n/n = O(1) ✓

Quick Check

Q1. Which is faster for large n: O(n log n) or O(n²)?

Answer: O(n log n) — log n grows much slower than n.

Q2. T(n) = 3T(n/3) + n. What is the time complexity?

Answer: a=3, b=3, p=log₃3=1. f(n)=n=Θ(n^1) → Case 2 → T(n) = Θ(n log n).

Q3. T(n) = 4T(n/2) + n. What is the time complexity?

Answer: a=4, b=2, p=log₂4=2. f(n)=n=O(n^(2-1)) → Case 1 → T(n) = Θ(n²).

Key Formulas

  • Master Theorem Case 1: f(n) = O(n^(log_b a − ε)) → T(n) = Θ(n^log_b a)
  • Master Theorem Case 2: f(n) = Θ(n^log_b a) → T(n) = Θ(n^log_b a · log n)
  • Master Theorem Case 3: f(n) = Ω(n^(log_b a + ε)) → T(n) = Θ(f(n))

GATE Exam Tips

  • ★Always compute p = log_b(a) first before deciding which Master Theorem case applies
  • ★T(n) = T(n/2) + T(n/4) + n: Master Theorem does NOT apply — use recursion tree
  • ★Amortised ≠ average-case. Amortised is worst-case over a sequence.
  • ★O only says "at most"; Θ says "exactly". GATE distinguishes them carefully.

Finished reading this topic?

Mark it complete to track your study progress.

Sign in to track