Algorithm Analysis: Asymptotic Notation, Recurrences and Worked Examples for GATE CS

You can write the code, yet freeze when a GATE question asks for the time complexity of a fragment or an interviewer asks whether you can beat O(n^2). Algorithm analysis is not a collection of Big-O tables to memorise. It is one habit: turn the code into a count of operations as a function of n, then decide which term still matters as n grows. A loop nest becomes a sum, a recursive call becomes a recurrence, and a doubling array becomes a cost charged across a whole sequence of pushes.

Algorithm analysis starts with a cost model: best, worst and average case

We count comparisons, assignments and arithmetic as unit-cost operations on a RAM-style machine, as a function of input size n. Ignoring machine speed and constants lets us predict the growth curve, not milliseconds.

Consider linear search on an array of 100 elements. If the target is first, the best case takes 1 comparison. If it is last or absent, the worst case takes 100. For a uniformly random successful search, the average is (1 + 2 + ... + 100) / 100 = 50.5 comparisons. GATE and interviews normally expect worst-case analysis unless the question specifies another case.

Space complexity applies the same idea to extra memory. Recursion depth counts too: a recursion that goes n calls deep uses Theta(n) stack space even if each call allocates no separate data structure.

Big-O, Big-Omega and Big-Theta, with the growth ladder at n = 16

Big-O is an asymptotic upper bound, Big-Omega is a lower bound, and Big-Theta is a tight bound from both sides. Formally, f(n) = O(g(n)) if constants c > 0 and n0 exist such that f(n) <= c*g(n) for every n >= n0.

This distinction matters. Saying quicksort's worst case is O(n^2) is true, but saying it is Theta(n^2) is stronger because it gives a tight class.

At n = 16, the common growth functions have these exact values:

log2 n and sqrt(n) tie here, but the square-root function stays ahead afterwards. At n = 256, their values are 8 and 16. This is why small inputs can mislead.

Know this ladder: 1 < log n < sqrt(n) < n < n log n < n^2 < n^3 < 2^n < n!. Constants and lower-order terms disappear only when reporting an asymptotic class. Keep them in an exact-count NAT answer.

Counting operations: turning loop nests into sums

Turn loops into sums. For this fragment:

for i = 1 to n
    for j = 1 to i
        work

The inner statement runs 1 + 2 + ... + n = n(n + 1)/2 times. At n = 8, that is 8 * 9 / 2 = 36 executions. The exact answer is 36, while the asymptotic answer is Theta(n^2).

Now compare a halving loop: while (n > 1) n = n / 2. It runs floor(log2 n) times. At n = 64, its six start-of-iteration values are 64, 32, 16, 8, 4 and 2, after which n becomes 1. Additive stepping commonly produces polynomial counts; multiplicative stepping commonly produces logarithmic counts.

GATE can dress up the same reasoning in two ways. A NAT asks for the exact count, such as 36. An MCQ asks for the Theta class. Do not answer one costume with the other.

Recurrences: build the recursion tree, then reach for the Master theorem

Take T(n) = 2T(n/2) + n, with T(1) = 1, at n = 16. The root contributes 16 work. Its children contribute 8 + 8 = 16, then four nodes contribute 4 + 4 + 4 + 4 = 16, and eight nodes contribute 16 again.

There are log2 16 = 4 internal levels costing 16 each, plus 16 leaves costing 1 each. The exact total is 16 * 4 + 16 = 80. Generally, log n levels do n work each, giving Theta(n log n), the merge-sort bound.

For T(n) = aT(n/b) + f(n), the Master theorem compares f(n) with n^(log_b a):

1. If f(n) is polynomially smaller, the recursive work wins and T(n) = Theta(n^(log_b a)).

2. If f(n) = Theta(n^(log_b a) log^k n), then T(n) = Theta(n^(log_b a) log^(k+1) n).

3. If f(n) is polynomially larger and the regularity condition holds, T(n) = Theta(f(n)).

For T(n) = 8T(n/2) + n^2, the benchmark is n^(log2 8) = n^3. Since n^2 is polynomially smaller, case 1 gives Theta(n^3). For T(n) = 2T(n/2) + n^2, the benchmark is n, so case 3 gives Theta(n^2).

The standard theorem does not cover every recurrence. T(n) = 2T(n/2) + n/log n, for example, falls into its gap. Build a recursion tree when the cases do not fit.

Amortized analysis: what a dynamic-array push really costs

A dynamic array push is usually O(1), but a push that triggers doubling copies the existing elements. Start with capacity 1 and push 32 elements. The expansions copy 1 + 2 + 4 + 8 + 16 = 31 elements. Add 32 writes for the pushes, and the whole sequence costs 63 operations, or 63/32, which is under 2 per push.

That gives O(1) amortized time per push and O(n) for n pushes. Amortized analysis guarantees an average over any operation sequence; it is not a statement about probability.

Algorithm-analysis traps that cost marks

• Treating O as exact. Every Theta(n) function is also O(n^2). In an MSQ, the looser upper-bound option may still be true. Check the definition, not which option feels tightest.

• Mixing average and worst case. Quicksort is Theta(n log n) on average but Theta(n^2) in the worst case, such as sorted input with a fixed-end pivot. Use worst case unless another case is named.

• Dropping constants in an exact count. Logarithm bases differ by a constant, so O(log2 n) and O(log10 n) are the same class. A NAT asking for iterations still needs the specified base and exact constant.

• Trusting the visible term at small n. n^2 + 1000n is Theta(n^2), although the linear term is at least as large up to n = 1000. Compare eventual growth, not one sample input.

How GATE and interviews test algorithm analysis

Algorithm-analysis questions arrive in four recognisable shapes: classify a code fragment, solve a recurrence, calculate an exact NAT count, or judge several asymptotic statements in an MSQ. Marks per question, negative marking and the paper's NAT and MSQ split are fixed each cycle in the official GATE information brochure, so work from the current one rather than an older summary. Then use GATE CS Subject Weightage: Where Your Study Hours Actually Pay Off to place Algorithms inside your wider plan.

An interview asks for the complexity of the solution you just wrote, a line-by-line justification, and often an improvement. Turning loops into sums is exactly what “walk me through the complexity” means. Trees and graphs often drive the follow-up, so Binary Trees and Binary Search Trees is a useful next foundation.

After each concept, solve a mixed set under time. The GATE Test Series provides topic-wise tests and full mocks where exact counts, recurrence solving and asymptotic comparisons appear together.

The short version, and where to go next

• Translate operations into sums.

• Know the growth ladder without hesitation.

• Build the recursion tree first, then use the Master theorem as a shortcut.

• Assume worst case unless another case is named.

• Read amortized cost as a guarantee over a sequence, not a probability.

Organise your Algorithms study around these ideas. Sorting, divide and conquer, greedy methods and dynamic programming deserve focused drills next. For a structured path through Algorithms and core CS, use the Zero to Hero Complete CS Course, then browse the GATE CS Preparation hub for the other subject pillars.