IN THE CS SYLLABUS

Asymptotic complexity and recurrences

Asymptotic complexity describes how an algorithm's time and space grow with input size $n$ , independent of any machine. It is expressed with the notations $O$ , $Ω$ , $Θ$ , $o$ and $ω$ and found by counting loops or solving recurrences (substitution, recursion tree, Master theorem). The two core skills here are counting exactly how many times a statement executes, and solving a recurrence for a recursive algorithm's running time. Every example is traced in full.

14 previous-year questions · 14 solved · 6 practice questions

1. Why asymptotic analysis, and the five notations

Asymptotic complexity describes how the running time (or memory used) of a program grows as the input size $n$ becomes large, ignoring machine-dependent constants and lower-order terms. Conventions used throughout these notes:

$n$ is a positive integer.
The functions compared are non-negative for large $n$ .
Logarithms are base 2 unless stated otherwise.
int is 4 bytes and char is 1 byte; arrays are stored row-major.
The worst case is meant whenever a question does not say otherwise.
Space complexity means auxiliary (extra) space, not counting the input, unless stated otherwise.

Each notation is a set of functions bounded relative to a reference function $g (n)$ . $O$ , $Ω$ and $Θ$ allow the bound to be tight. $o$ and $ω$ describe strict bounds: $f$ grows strictly slower or strictly faster than $g$ .

BIG-O (UPPER BOUND)

f (n) = O (g (n)) ⟺ \exists c > 0, n_{0} > 0 such that 0 \leq f (n) \leq c \cdot g (n) \forall n \geq n_{0}

$f$ grows no faster than $g$ , up to a constant factor.

BIG-OMEGA (LOWER BOUND)

f (n) = Ω (g (n)) ⟺ \exists c > 0, n_{0} > 0 such that 0 \leq c \cdot g (n) \leq f (n) \forall n \geq n_{0}

$f$ grows at least as fast as $g$ , up to a constant factor.

BIG-THETA (TIGHT BOUND)

f (n) = Θ (g (n)) ⟺ \exists c_{1}, c_{2} > 0, n_{0} > 0 such that 0 \leq c_{1} g (n) \leq f (n) \leq c_{2} g (n) \forall n \geq n_{0}

$f$ and $g$ grow at the same rate. Equivalently, $f = O (g)$ and $f = Ω (g)$ both hold.

LITTLE-O (STRICT UPPER BOUND)

f (n) = o (g (n)) ⟺ \forall c > 0 \exists n_{0} > 0 such that 0 \leq f (n) < c \cdot g (n) \forall n \geq n_{0}

The inequality must hold for EVERY $c > 0$ , not just for some $c$ (contrast with $O$ ). When $g (n) > 0$ for all large $n$ , this is equivalent to $lim_{n \to \infty} f (n) / g (n) = 0$ .

LITTLE-OMEGA (STRICT LOWER BOUND)

f (n) = ω (g (n)) ⟺ \forall c > 0 \exists n_{0} > 0 such that 0 \leq c \cdot g (n) < f (n) \forall n \geq n_{0}

When $g (n) > 0$ for all large $n$ , this is equivalent to $lim_{n \to \infty} f (n) / g (n) = \infty$ .

Properties of the notations

$f = Θ (g) ⟺ f = O (g)$ and $f = Ω (g)$ .
Transpose symmetry: $f = O (g) ⟺ g = Ω (f)$ , and $f = o (g) ⟺ g = ω (f)$ .
Symmetry: $f = Θ (g) ⟺ g = Θ (f)$ .
Transitivity: all five notations are transitive. For example, $f = O (g)$ and $g = O (h)$ give $f = O (h)$ .
Reflexivity: $f = O (f)$ , $f = Ω (f)$ and $f = Θ (f)$ . However, $f$ is never $o (f)$ or $ω (f)$ .
Constant factors: $c \cdot f = Θ (f)$ for any constant $c > 0$ .
Sum rule: $f_{1} + f_{2} = Θ (max (f_{1}, f_{2}))$ for non-negative functions. Hence a polynomial of degree $d$ with positive leading coefficient is $Θ (n^{d})$ .
Product rule: if $f_{1} = O (g_{1})$ and $f_{2} = O (g_{2})$ then $f_{1} f_{2} = O (g_{1} g_{2})$ .
The base of a logarithm does not matter: $lo g_{a} n = Θ (lo g_{b} n)$ for constants $a, b > 1$ . Also, $lo g (n^{k}) = k lo g n = Θ (lo g n)$ .
The base of an exponential DOES matter: $2^{n} = o (3^{n})$ . Also, $2^{n + 1} = 2 \cdot 2^{n} = Θ (2^{n})$ , but $2^{2 n} = 4^{n}$ is NOT $O (2^{n})$ .

CHANGE OF BASE FOR LOGARITHMS

lo g_{a} n = \frac{lo g _{b} n}{lo g _{b} a} (a, b > 1 constants)

The two logarithms differ only by the constant factor $1/ lo g_{b} a$ , which is why the base is irrelevant inside $O$ , $Ω$ and $Θ$ .

EXAM TIP

A fast way to compare two given functions $f$ and $g$ is to compute $lim_{n \to \infty} f (n) / g (n)$ :

If the limit is 0, then $f = o (g)$ . Hence $f = O (g)$ , but NOT $Θ (g)$ .
If it is a finite positive constant, then $f = Θ (g)$ .
If it is $\infty$ , then $f = ω (g)$ . Hence $f = Ω (g)$ , but NOT $Θ (g)$ .

If the limit does NOT exist, the test tells you nothing, so go back to the definitions. For example, $f (n) = n (2 + sin n)$ is $Θ (n)$ even though $f (n) / n$ has no limit.

EXAM TIP

Comparing logarithms is a useful trick, but it has a trap. If $lo g f (n) - lo g g (n) \to + \infty$ , then $f = ω (g)$ . But $lo g f = Θ (lo g g)$ does NOT imply $f = Θ (g)$ . For example, $lo g (n^{2}) = 2 lo g n = Θ (lo g n)$ , yet $n^{2}$ is not $O (n)$ .

EXAM TIP

$Θ$ is the only one of these notations that fixes the growth rate from both sides. An $O$ bound is only an upper bound. An algorithm that takes $Θ (n^{2})$ time is also $O (n^{3})$ , and the statement 'its running time is $O (n^{3})$ ' is TRUE. So read the question carefully:

If it asks which statements are true, a loose $O$ bound counts as true.
If it asks for THE complexity and offers several options, choose the tight bound (the $Θ$ bound), even when the options are written with $O$ .

2. Ordering growth rates

A common task is to order a mixed list of functions (logarithmic, polynomial, exponential, factorial) from slowest-growing to fastest-growing. The chain below is the reference. To place a function that is not in it, simplify the function first, then use the limit test.

Standard growth-rate ordering (slowest to fastest)

$1$ (constant)
$lo g lo g n$
$lo g n$
$(lo g n)^{k}$ for a constant $k > 1$ (polylogarithmic)
$n = n^{0.5}$ (and, in general, $n^{ϵ}$ for a constant $0 < ϵ < 1$ )
$n$ (linear)
$n lo g n$
$n^{2}$
$n^{3}$ and higher fixed powers $n^{k}$ ( $k$ constant)
$c^{n}$ for a constant $c > 1$ , e.g. $2^{n}$ . Different bases are different rates: $2^{n} = o (3^{n})$ .
$n!$
$n^{n}$

LOG VS POLYNOMIAL VS EXPONENTIAL VS FACTORIAL

n \to \infty lim \frac{( lo g n ) ^{k}}{n ^{ϵ}} = 0, n \to \infty lim \frac{n ^{k}}{c ^{n}} = 0, n \to \infty lim \frac{c ^{n}}{n !} = 0 (k any constant, ϵ > 0, c > 1)

These three limits give the dominance rules:

Any positive power of $n$ beats any power of $lo g n$ .
Any exponential with base greater than 1 beats any fixed power of $n$ .
$n!$ beats any exponential with a constant base.

STIRLING'S APPROXIMATION AND LOG(N!)

n! = Θ (2 π n (\frac{n}{e})^{n}), lo g (n!) = Θ (n lo g n)

Consequences:

$2^{n} = o (n!)$ and $n! = o (n^{n})$ .
The elementary bounds $(n /2)^{n /2} \leq n! \leq n^{n}$ are enough on their own to give $lo g (n!) = Θ (n lo g n)$ .
This result is behind the $Ω (n lo g n)$ lower bound on the number of comparisons for comparison-based sorting: a decision tree with $n!$ leaves has height at least $lo g (n!)$ .

EXPONENT-LOG SWAP IDENTITY

a^{l o g_{b} n} = n^{l o g_{b} a} (a > 0, b > 1)

Take $lo g_{b}$ of both sides: each becomes $lo g_{b} n \cdot lo g_{b} a$ . Examples: $2^{l o g_{2} n} = n$ , $4^{l o g_{2} n} = n^{2}$ , $2^{l o g_{4} n} = n$ , $3^{l o g_{2} n} = n^{l o g_{2} 3}$ .

WORKED EXAMPLE

Order the following functions from slowest to fastest growing: $n lo g n$ , $2^{l o g n}$ , $n^{2} / lo g n$ , $n lo g n$ , $(lo g n)^{l o g n}$ (logarithms base 2).

Solution

Simplify $2^{l o g_{2} n} = n$ , a linear function.
$n lo g n = n^{0.5} (lo g n)^{0.5}$ . Its ratio to $n$ is $lo g n / n \to 0$ , so it is sub-linear.
$n lo g n$ grows faster than $n$ , because the ratio is $lo g n \to \infty$ .
Compare $n^{2} / lo g n$ with $n lo g n$ . The ratio is $n / (lo g n)^{2} \to \infty$ , so $n^{2} / lo g n$ is faster.
$(lo g n)^{l o g n} = 2^{(l o g n) (l o g l o g n)} = (2^{l o g n})^{l o g l o g n} = n^{l o g l o g n}$ . Its exponent $lo g lo g n$ grows without bound, so it eventually exceeds every fixed power of $n$ , including $n^{2} / lo g n$ .
Final order: $n lo g n < 2^{l o g n} < n lo g n < n^{2} / lo g n < (lo g n)^{l o g n}$ .

Answer: $n lo g n < 2^{l o g n} < n lo g n < n^{2} / lo g n < (lo g n)^{l o g n}$

EXAM TIP

With log base 2, $2^{l o g n}$ is exactly $n$ , not an exponential function of $n$ . Always check the base of the power against the base of the logarithm. Unlike $lo g n$ on its own, where the base only changes a constant factor, the base here changes the growth rate: $4^{l o g_{2} n} = n^{2}$ but $2^{l o g_{4} n} = n$ .

3. Analysing loops: independent, nested and dependent

To find the complexity of a piece of code, count how many times the innermost statement executes as a function of $n$ , then simplify to the dominant term. Work from the inside out:

1. Find the innermost loop's iteration count in terms of the surrounding loop variables.
2. Sum (or multiply) across the outer loops.

Procedure for analysing loops

Identify the statement whose execution count you are asked for, often the innermost body.
A step loop for (i = a; i <= b; i += k) with integer $k \geq 1$ runs $⌊(b - a) / k ⌋ + 1 = ⌈(b - a + 1) / k ⌉$ times when $a \leq b$ , and 0 times when $a > b$ .
For independent nested loops (the inner bound does not depend on the outer variable), multiply the iteration counts.
For dependent nested loops (for example for (j = 1; j <= i; j++)), write the total as a summation over the outer variable and evaluate it in closed form.
A loop that multiplies its index by a constant $c \geq 2$ (e.g. i *= 2) runs $Θ (lo g n)$ times. This needs a start value i >= 1: starting from i = 0, the index never grows. A loop that divides by 2 (i /= 2, from n down to 1) is also $Θ (lo g n)$ .
A loop that squares its index (i = i * i, starting from i = 2) runs $Θ (lo g lo g n)$ times. A loop for (i = 1; i * i <= n; i++) runs $⌊ n ⌋$ times.
Drop lower-order terms and constant factors only at the very end, after the exact count is found.

ARITHMETIC SERIES

i = 1 \sum n i = \frac{n ( n + 1 )}{2} = Θ (n^{2})

This is the count when the inner loop runs exactly $i$ times as $i$ goes from 1 to $n$ . If the inner loop runs $n - i$ times, the exact count changes to $n (n - 1) /2$ , and $k i + c$ times gives $k n (n + 1) /2 + c n$ . Both are still $Θ (n^{2})$ when $k > 0$ .

SUMS OF POWERS

i = 1 \sum n i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6} = Θ (n^{3}), i = 1 \sum n i^{k} = Θ (n^{k + 1}) (k \geq 0 constant)

This applies to triple loops such as $i$ from 1 to $n$ , $j$ from 1 to $i$ , $k$ from 1 to $j$ , and to inner loops that run $i^{2}$ times.

GEOMETRIC SERIES

k = 0 \sum m r^{k} = \frac{r ^{m + 1} - 1}{r - 1} (r \neq = 1), k = 0 \sum l o g_{2} n 2^{k} = 2 n - 1 (n a power of 2)

When $r > 1$ , the sum is $Θ (its largest term)$ . When $0 < r < 1$ , it is $Θ (1)$ .

HARMONIC SERIES AND LOG(N!)

i = 1 \sum n \frac{1}{i} = ln n + O (1) = Θ (lo g n), i = 1 \sum n lo g i = lo g (n!) = Θ (n lo g n)

The harmonic sum appears when an inner loop steps by the outer index (inner count about $n / i$ ). The $lo g (n!)$ sum appears when an inner loop runs $lo g i$ times.

MULTIPLICATIVE (LOGARITHMIC) LOOP

i = 1, c, c^{2}, \dots \leq n gives ⌊ lo g_{c} n ⌋ + 1 = Θ (lo g n) iterations (integer c \geq 2, n \geq 1)

This is the exact count for for (i = 1; i <= n; i *= c). For example, with $c = 2$ and $n = 1024$ the loop runs $10 + 1 = 11$ times, not 10.

WORKED EXAMPLE

Determine the exact number of times x++; executes as a function of $n$ ( $n$ a power of 2) for the code below, then give its $Θ$ complexity.

int x = 0;
for (int i = 1; i <= n; i = i * 2) {
    for (int j = 1; j <= i; j++) {
        x++;
    }
}

Solution

Outer loop: $i$ takes the values $1, 2, 4, \dots, n = 2^{l o g_{2} n}$ , so it runs $lo g_{2} n + 1$ times.
For each value of $i$ , the inner loop runs exactly $i$ times.
Total count $= \sum_{k = 0}^{l o g_{2} n} 2^{k} = 2^{l o g_{2} n + 1} - 1 = 2 n - 1$ (geometric series).
So x++ executes exactly $2 n - 1$ times (for example, 15 times when $n = 8$ ). The complexity is $Θ (n)$ , NOT $Θ (n lo g n)$ , even though there are two nested loops and the outer one is logarithmic. This is a common trap.

Answer: Exactly $2 n - 1$ executions; $Θ (n)$ .

WORKED EXAMPLE

Give the $Θ$ complexity of the number of times x++; executes.

int x = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        x++;
    }
}

Solution

For a fixed $i$ , $j$ takes the values $1, 1 + i, 1 + 2 i, \dots \leq n$ . So the inner loop runs $⌊(n - 1) / i ⌋ + 1 = ⌈ n / i ⌉$ times.
The total is $\sum_{i = 1}^{n} ⌈ n / i ⌉$ . Each term lies between $n / i$ and $n / i + 1$ .
So the total lies between $n \sum_{i = 1}^{n} 1/ i$ and $n \sum_{i = 1}^{n} 1/ i + n$ . The harmonic sum is $Θ (lo g n)$ , so the total is $Θ (n lo g n)$ .

Answer: $Θ (n lo g n)$

EXAM TIP

Two nested loops do NOT automatically mean $Θ (n^{2})$ , or even $Θ (n lo g n)$ . Always compute the actual sum. In the first example above, a geometric series inside a logarithmic outer loop collapses to linear. In the second, an inner step of $i$ turns a $Θ (n^{2})$ -looking loop into $Θ (n lo g n)$ .

4. Recurrence relations: substitution and recursion tree

A recursive algorithm's running time is naturally expressed as a recurrence: an equation that gives $T (n)$ in terms of $T$ on smaller inputs. Two general methods also handle recurrences that the Master theorem cannot:

Substitution (unrolling): expand the recurrence repeatedly, or guess the answer and verify it by induction.
Recursion tree: draw the calls as a tree and add up the work level by level.

Substitution method (unrolling), step by step

Write the recurrence for $T (n)$ , then for $T (n / b)$ or $T (n - 1)$ by substituting into the same formula.
Repeat the substitution $k$ times until the base case $T (1)$ (or $T (n_{0})$ ) appears.
Express the accumulated non-recursive work as a summation over the $k$ substitutions.
Determine $k$ in terms of $n$ : for example $n / b^{k} = 1 \Rightarrow k = lo g_{b} n$ , or $k = n - 1$ for a $T (n - 1)$ recurrence with base case $T (1)$ .
Evaluate the summation in closed form and simplify to $Θ$ notation.

Recursion tree method, step by step

Draw the tree. Each node is a subproblem, labelled with its input size and the non-recursive work done at that call.
Determine the branching factor $a$ (children per node) and how the size shrinks per level, for example $n / b$ .
Compute the total non-recursive work at each level of the tree.
Determine the depth of the tree: the level at which the size reaches the base case.
Add the per-level totals, including the leaves (number of leaves × base-case cost), to get $T (n)$ .

WORKED EXAMPLE

Solve $T (n) = 2 T (n /2) + n$ , $T (1) = 1$ , for $n$ a power of 2, using a recursion tree.

Solution

Level 0 (root): 1 node of size $n$ ; non-recursive work $= n$ .
Level 1: 2 nodes of size $n /2$ ; total work $= 2 \times (n /2) = n$ .
Level $i$ : $2^{i}$ nodes of size $n / 2^{i}$ ; total work $= 2^{i} \times (n / 2^{i}) = n$ . Every internal level contributes exactly $n$ .
The size reaches 1 when $n / 2^{i} = 1$ , i.e. $i = lo g_{2} n$ . So levels $0$ to $lo g_{2} n - 1$ are internal, which gives $lo g_{2} n$ levels of work $n$ each.
The leaf level has $2^{l o g_{2} n} = n$ leaves, each costing $T (1) = 1$ , for a total of $n$ .
Total: $T (n) = n lo g_{2} n + n = Θ (n lo g n)$ . Check: $T (8) = 8 \cdot 3 + 8 = 32$ .

Answer: $T (n) = n lo g_{2} n + n = Θ (n lo g n)$

EXAM TIP

The shape of the per-level totals decides the answer:

Equal at every level: the answer is (work per level) × (number of levels). This is Master theorem Case 2.
Shrinking GEOMETRICALLY going down (each level at most a constant fraction $< 1$ of the one above): the root dominates, and the total is $Θ (root’s work)$ . This is Case 3.
Growing GEOMETRICALLY going down: the leaves dominate, and the total is $Θ (number of leaves)$ . This is Case 1.

The word 'geometrically' matters. In $T (n) = 2 T (n /2) + n / lo g n$ , level $i$ contributes $n / (lo g n - i)$ . The levels shrink going down, but not geometrically, so the root does not dominate. The sum is $n \sum_{j = 1}^{l o g n} 1/ j = Θ (n lo g lo g n)$ .

Standard recurrences to recognise

Recurrence	Solution	Typical source
$T (n) = T (n /2) + Θ (1)$	$Θ (lo g n)$	Binary search (worst case)
$T (n) = 2 T (n /2) + Θ (1)$	$Θ (n)$	Recursive divide-in-half with constant combine, e.g. maximum of an array
$T (n) = T (n /2) + Θ (n)$	$Θ (n)$	Halving with linear work per call
$T (n) = 2 T (n /2) + Θ (n)$	$Θ (n lo g n)$	Merge sort
$T (n) = T (n - 1) + Θ (1)$	$Θ (n)$	Linear recursion, e.g. recursive factorial
$T (n) = T (n - 1) + Θ (n)$	$Θ (n^{2})$	Quicksort worst case (always the most unbalanced split)
$T (n) = 2 T (n - 1) + Θ (1)$	$Θ (2^{n})$	Tower of Hanoi: exactly $2^{n} - 1$ moves when $T (1) = 1$
$T (n) = T (n - 1) + T (n - 2) + Θ (1)$	$Θ (φ^{n})$ , $φ = \frac{1 + 5}{2} \approx 1.618$	Naive recursive Fibonacci; this is $O (2^{n})$ but NOT $Θ (2^{n})$
$T (n) = T (n) + Θ (1)$	$Θ (lo g lo g n)$	Repeated square-rooting of the size

5. The Master theorem

The Master theorem gives a direct closed-form answer for recurrences of the form $T (n) = a T (n / b) + f (n)$ . It requires:

constants $a \geq 1$ and $b > 1$ ;
$f (n)$ asymptotically positive.

The answer does not change if $n / b$ is read as $⌊ n / b ⌋$ or $⌈ n / b ⌉$ .

The theorem does NOT apply to:

subtractive recurrences such as $T (n) = 2 T (n - 1) + 1$ ;
unequal-size subproblems such as $T (n) = T (n /2) + T (n /3) + n$ ;
non-constant $a$ or $b$ , as in $T (n) = n T (n) + n$ .

These need substitution, a recursion tree or a change of variables.

MASTER THEOREM: GENERAL FORM

T (n) = a T (\frac{n}{b}) + f (n), a \geq 1, b > 1

$a$ is the number of subproblems, $b$ is the factor by which the size shrinks, and $f (n)$ is the work done outside the recursive calls (dividing plus combining). Compare $f (n)$ with $n^{l o g_{b} a}$ , which is the number of leaves of the recursion tree.

Master theorem: the three cases

Case	Condition on f(n)	Result
1	$f (n) = O (n^{l o g_{b} a - ϵ})$ for some constant $ϵ > 0$ ( $f$ smaller by a polynomial factor)	$T (n) = Θ (n^{l o g_{b} a})$
2	$f (n) = Θ (n^{l o g_{b} a} lo g^{k} n)$ for some constant $k \geq 0$ ( $f$ equal, times an optional log power). The basic theorem states only $k = 0$ ; $k \geq 0$ is the standard extended form.	$T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n)$
3	$f (n) = Ω (n^{l o g_{b} a + ϵ})$ for some constant $ϵ > 0$ , AND the regularity condition $a f (n / b) \leq c f (n)$ holds for some constant $c < 1$ and all large $n$ . Regularity holds automatically for $f (n) = n^{d}$ or $n^{d} lo g^{k} n$ with $d > lo g_{b} a$ .	$T (n) = Θ (f (n))$

MASTER THEOREM FOR POLYNOMIAL F(N)

T (n) = a T (\frac{n}{b}) + Θ (n^{d}) ⟹ T (n) = ⎩ ⎨ ⎧ Θ (n^{l o g_{b} a}) Θ (n^{d} lo g n) Θ (n^{d}) d < lo g_{b} a d = lo g_{b} a d > lo g_{b} a

This is the special case $f (n) = Θ (n^{d})$ with $d \geq 0$ a constant. It is the quickest form to apply when $f$ has no log factor.

Applying the Master theorem, step by step

Read off $a$ , $b$ and $f (n)$ from the recurrence, and check that $a \geq 1$ and $b > 1$ are constants.
Compute the critical exponent $lo g_{b} a$ , which gives the comparison function $n^{l o g_{b} a}$ .
Compare $f (n)$ with $n^{l o g_{b} a}$ . Is it polynomially smaller (Case 1), the same order possibly times $lo g^{k} n$ with $k \geq 0$ (Case 2), or polynomially larger with regularity (Case 3)?
If $f (n)$ is smaller or larger only by a LOG factor, the basic three-case theorem does not apply. For example, $f (n) = n^{l o g_{b} a} / lo g n$ is smaller, but not polynomially. The standard extension covers these: $f (n) = Θ (n^{l o g_{b} a} lo g^{k} n)$ gives $T (n) = Θ (n^{l o g_{b} a} lo g lo g n)$ when $k = - 1$ , and $T (n) = Θ (n^{l o g_{b} a})$ when $k < - 1$ . Otherwise, use a recursion tree.
State the final answer in $Θ$ notation using the matched case.

WORKED EXAMPLE

Solve $T (n) = 8 T (n /2) + n^{2}$ , $T (1) = 1$ .

Solution

$a = 8$ , $b = 2$ , $f (n) = n^{2}$ .
Critical exponent: $lo g_{2} 8 = 3$ , so compare $f$ with $n^{3}$ .
$f (n) = n^{2} = O (n^{3 - 1})$ : polynomially smaller than $n^{3}$ with $ϵ = 1$ . This is Case 1.
By Case 1, $T (n) = Θ (n^{l o g_{b} a}) = Θ (n^{3})$ .

Answer: $T (n) = Θ (n^{3})$

WORKED EXAMPLE

Solve $T (n) = 2 T (n) + lo g n$ , with $T (n) = Θ (1)$ for $n \leq 2$ .

Solution

The size shrinks by square-rooting, not by a constant factor, so the Master theorem does not apply directly. Change variables.
Let $m = lo g_{2} n$ , so $n = 2^{m}$ and $n = 2^{m /2}$ . Define $S (m) = T (2^{m})$ .
The recurrence becomes $S (m) = 2 S (m /2) + m$ .
For $S$ : $a = 2$ , $b = 2$ , $m^{l o g_{2} 2} = m$ , and $f (m) = m$ . This is Case 2 with $k = 0$ , so $S (m) = Θ (m lo g m)$ .
Substitute back $m = lo g n$ : $T (n) = Θ (lo g n \cdot lo g lo g n)$ .

Answer: $T (n) = Θ (lo g n lo g lo g n)$

EXAM TIP

Do not apply the Master theorem to a SUBTRACTIVE recurrence. $T (n) = T (n - 1) + T (n - 2) + O (1)$ and $T (n) = 2 T (n - 1) + O (1)$ are not of the form $a T (n / b) + f (n)$ ; solve them by substitution or a recursion tree. Those two are exponential in $n$ . Not every subtractive recurrence is: $T (n) = T (n - 1) + n$ is $Θ (n^{2})$ and $T (n) = T (n - 1) + 1$ is $Θ (n)$ .

6. Space complexity, and best/worst/average case

Space complexity counts the memory an algorithm uses as a function of $n$ . In these notes it means auxiliary space, the memory beyond the input itself:

recursion stack frames;
auxiliary arrays;
extra pointers and counters.

Some texts also count the input. Say which one you mean when you work a problem.

Best, worst and average case describe how the running time varies across different inputs of the SAME size $n$ , not across different sizes.

Reading space complexity off code

Iterative code with only a fixed number of scalar variables (no arrays sized by $n$ ) uses $O (1)$ auxiliary space.
An auxiliary array or table sized in proportion to $n$ (e.g. a DP table or an output array) contributes $Θ (n)$ space; a 2-D $n \times n$ table contributes $Θ (n^{2})$ .
For recursive code, the space is the MAXIMUM DEPTH of the call stack at any moment times the space per frame, not the total number of calls made.
Two recursive calls made one after the other reuse the same stack depth. The function f(n-1) + f(n-1) takes $Θ (2^{n})$ time but only $Θ (n)$ stack space.
These notes assume no tail-call optimisation: a recursive call uses a new stack frame even when it is the last action of the function, unless a question says otherwise.

WORKED EXAMPLE

What is the auxiliary space complexity of the recursive factorial function below, for input $n \geq 1$ ?

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

Solution

Each call to fact pushes one stack frame. The frame stays on the stack until its recursive call returns, because the multiplication happens afterwards.
The deepest point is when fact(1) is reached. At that moment fact(n), fact(n-1), ..., fact(1) are all active: $n$ frames, each of constant size.
Auxiliary space is proportional to the maximum stack depth $n$ , i.e. $Θ (n)$ , even though the function uses no arrays.

Answer: $Θ (n)$

Best, worst, and average case

Case	Meaning	When it is used
Worst case	The maximum running time over ALL inputs of size $n$	The default meaning of 'complexity' unless stated otherwise; it gives a guarantee
Best case	The minimum running time over all inputs of size $n$	For example, insertion sort on an already-sorted array takes $Θ (n)$
Average case	The expected running time over a specified distribution of inputs, often 'all permutations equally likely'	Needs a stated or implied probability distribution; without one, 'average case' is not defined

EXAM TIP

Best/worst/average case and the $O /Ω/Θ$ notations are two separate axes:

Best/worst/average case is about INPUT VARIATION at a fixed size $n$ .
$O$ , $Ω$ and $Θ$ are about GROWTH RATE as $n$ varies.

It is valid to say 'the worst-case time is $Θ (n^{2})$ ' (a tight bound on the worst case) or 'the best-case time is $Θ (n)$ '. Do not read $Ω$ as 'best case' or $O$ as 'worst case'.

PREVIOUS-YEAR QUESTIONS

14 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020

GATE 2026 CS1 Q.17

GATE 2026 · CS1Q.17 · 1 mark · MCQ

Consider the following recurrence relations:

For all $n > 1$ ,
$T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n)$
$T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n)$

Assume that for all $n \leq 1$ , $T_{1} (n) = 1$ and $T_{2} (n) = 1$ .

Which one of the following options is correct?

(A)
$T_{1} (n) = Θ (n^{2})$
(B)
$T_{1} (n) = Θ (n^{2} lo g_{2} n)$
(C)
$T_{1} (n) = Θ (n^{l o g_{4} 5})$
(D)
$T_{1} (n) = Θ (n^{l o g_{4} 5} lo g_{2} n)$

Answer and solution

GATE 2026 CS1 Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.17: answer and solution

GATE 2026 CS2 Q.24

GATE 2026 · CS2Q.24 · 1 mark · MCQ

Consider the following functions, where $n$ is a positive integer.

n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)}

Which one of the following options lists the functions in increasing order of asymptotic growth rate?

Note: Assume the base of log to be 2.

(A)
$lo g (n)$ , $n^{1/3}$ , $2^{l o g (n)}$ , $lo g (n!)$
(B)
$n^{1/3}$ , $lo g (n)$ , $lo g (n!)$ , $2^{l o g (n)}$
(C)
$lo g (n)$ , $n^{1/3}$ , $lo g (n!)$ , $2^{l o g (n)}$
(D)
$2^{l o g (n)}$ , $n^{1/3}$ , $lo g (n)$ , $lo g (n!)$

Answer and solution

GATE 2026 CS2 Q.24: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.24: answer and solution

GATE 2026 CS2 Q.25

GATE 2026 · CS2Q.25 · 1 mark · MSQ

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $Θ (n)$ ?

(A)
$T (n) = T (n - 1) + 1, T (1) = 1$
(B)
$T (n) = 2 T (\frac{n}{2}) + 1, T (1) = 1$
(C)
$T (n) = 2 T (\frac{n}{2}) + n, T (1) = 1$
(D)
$T (n) = T (n - 1) + n, T (1) = 1$

Answer and solution

GATE 2026 CS2 Q.25: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.25: answer and solution

GATE 2026 CS2 Q.38

GATE 2026 · CS2Q.38 · 2 marks · MCQ

Consider an array $A$ of integers of size $n$ . The indices of $A$ run from $1$ to $n$ . An algorithm is to be designed to check whether $A$ satisfies the condition given below.

\forall i, j \in {1, \dots, n - 1} such that i > j, (A [i + 1] - A [i]) > (A [j + 1] - A [j])

Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?

(A)
$Θ (n)$
(B)
$Θ (lo g (n))$
(C)
$Θ (n lo g (n))$
(D)
$Θ (n^{2})$

Answer and solution

GATE 2026 CS2 Q.38: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.38: answer and solution

GATE 2025 CS1 Q.20

GATE 2025 · CS1Q.20 · 1 mark · MCQ

Consider the following recurrence relation:

T (n) = 2 T (n - 1) + n 2^{n} for n > 0, T (0) = 1.

Which ONE of the following options is CORRECT?

(A)
$T (n) = Θ (n^{2} 2^{n})$
(B)
$T (n) = Θ (n 2^{n})$
(C)
$T (n) = Θ ((lo g n)^{2} 2^{n})$
(D)
$T (n) = Θ (4^{n})$

Answer and solution

GATE 2025 CS1 Q.20: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.20: answer and solution

GATE 2025 CS2 Q.38

GATE 2025 · CS2Q.38 · 2 marks · MCQ

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size $n$ of these data structures?

(A)
P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n)$
(B)
P: $Θ (1)$ , Q: $Θ (n lo g n)$ , R: $Θ (n)$
(C)
P: $Θ (n)$ , Q: $Θ (n lo g n)$ , R: $Θ (n^{2})$
(D)
P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n lo g n)$

Answer and solution

GATE 2025 CS2 Q.38: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.38: answer and solution

GATE 2024 CS1 Q.17

GATE 2024 · CS1Q.17 · 1 mark · MCQ

Given an integer array of size $N$ , we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

(A)
both $O (N)$ and $Ω (N)$
(B)
$O (N)$ but not $Ω (N)$
(C)
$Ω (N)$ but not $O (N)$
(D)
neither $O (N)$ nor $Ω (N)$

Answer and solution

GATE 2024 CS1 Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.17: answer and solution

GATE 2024 CS1 Q.42

GATE 2024 · CS1Q.42 · 2 marks · MCQ

Consider the following recurrence relation:

T (n) = {n T (n) + n 1 for n \geq 1, for n = 1.

Which one of the following options is CORRECT?

(A)
$T (n) = Θ (n lo g lo g n)$
(B)
$T (n) = Θ (n lo g n)$
(C)
$T (n) = Θ (n^{2} lo g n)$
(D)
$T (n) = Θ (n^{2} lo g lo g n)$

Answer and solution

GATE 2024 CS1 Q.42: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.42: answer and solution

GATE 2024 CS2 Q.15

GATE 2024 · CS2Q.15 · 1 mark · MCQ

Let $T (n)$ be the recurrence relation defined as follows:

T (0) = 1, T (1) = 2, and T (n) = 5 T (n - 1) - 6 T (n - 2) for n \geq 2

Which one of the following statements is TRUE?

(A)
$T (n) = Θ (2^{n})$
(B)
$T (n) = Θ (n 2^{n})$
(C)
$T (n) = Θ (3^{n})$
(D)
$T (n) = Θ (n 3^{n})$

Answer and solution

GATE 2024 CS2 Q.15: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.15: answer and solution

GATE 2023 CS Q.29

GATE 2023 · CSQ.29 · 1 mark · MSQ

Let $f$ and $g$ be functions of natural numbers given by $f (n) = n$ and $g (n) = n^{2}$ . Which of the following statements is/are TRUE?

(A)
$f \in O (g)$
(B)
$f \in Ω (g)$
(C)
$f \in o (g)$
(D)
$f \in Θ (g)$

Answer and solution

GATE 2023 CS Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.29: answer and solution

GATE 2023 CS Q.54

GATE 2023 · CSQ.54 · 2 marks · MSQ

Consider functions Function_1 and Function_2 expressed in pseudocode as follows:

Function_1:

while n > 1 do
    for i = 1 to n do
        x = x + 1;
    end for
    n = ⌊n/2⌋;
end while

Function_2:

for i = 1 to 100*n do
    x = x + 1;
end for

Let $f_{1} (n)$ and $f_{2} (n)$ denote the number of times the statement " $x = x + 1$ " is executed in Function_1 and Function_2, respectively.

Which of the following statements is/are TRUE?

(A)
$f_{1} (n) \in Θ (f_{2} (n))$
(B)
$f_{1} (n) \in o (f_{2} (n))$
(C)
$f_{1} (n) \in ω (f_{2} (n))$
(D)
$f_{1} (n) \in O (n)$

Answer and solution

GATE 2023 CS Q.54: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.54: answer and solution

GATE 2022 CS Q.11

GATE 2022 · CSQ.11 · 1 mark · MCQ

Which one of the following statements is TRUE for all positive functions $f (n)$ ?

(A)
$f (n^{2}) = Θ (f (n)^{2})$ , when $f (n)$ is a polynomial
(B)
$f (n^{2}) = o (f (n)^{2})$
(C)
$f (n^{2}) = O (f (n)^{2})$ , when $f (n)$ is an exponential function
(D)
$f (n^{2}) = Ω (f (n)^{2})$

Answer and solution

GATE 2022 CS Q.11: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.11: answer and solution

GATE 2022 CS Q.51

GATE 2022 · CSQ.51 · 2 marks · MSQ

Consider the following recurrence:

f (1) f (2 n) f (2 n + 1) = 1; = 2 f (n) - 1, for n \geq 1; = 2 f (n) + 1, for n \geq 1.

Then, which of the following statements is/are TRUE?

(A)
$f (2^{n} - 1) = 2^{n} - 1$
(B)
$f (2^{n}) = 1$
(C)
$f (5 \cdot 2^{n}) = 2^{n + 1} + 1$
(D)
$f (2^{n} + 1) = 2^{n} + 1$

Answer and solution

GATE 2022 CS Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.51: answer and solution

GATE 2020 CS Q.2

GATE 2020 · CSQ.2 · 1 mark · MCQ

For parameters $a$ and $b$ , both of which are $ω (1)$ , $T (n) = T (n^{1/ a}) + 1$ , and $T (b) = 1$ .

Then $T (n)$ is

(A)
$Θ (lo g_{a} lo g_{b} n)$
(B)
$Θ (lo g_{ab} n)$
(C)
$Θ (lo g_{b} lo g_{a} n)$
(D)
$Θ (lo g_{2} lo g_{2} n)$

Answer and solution

GATE 2020 CS Q.2: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.2: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 12 marks · MCQ

Consider the recurrence $T (n) = 4 T (n /2) + n^{2} lo g n$ , with $T (1) = 1$ . Which of the following best describes $T (n)$ ?

(A)
$T (n) = Θ (n^{2})$
(B)
$T (n) = Θ (n^{2} lo g n)$
(C)
$T (n) = Θ (n^{2} lo g^{2} n)$
(D)
$T (n) = Θ (n^{3})$

Answer and solution

Answer: (C)

$a = 4$ , $b = 2$ , so $n^{l o g_{b} a} = n^{l o g_{2} 4} = n^{2}$ .
$f (n) = n^{2} lo g n = Θ (n^{l o g_{b} a} lo g^{k} n)$ with $k = 1$ .
This is Case 2 (with $k \geq 0$ ), so $T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n) = Θ (n^{2} lo g^{2} n)$ .
Check with a recursion tree ( $n$ a power of 2). Level $i$ has $4^{i}$ nodes of size $n / 2^{i}$ , each costing $(n / 2^{i})^{2} lo g (n / 2^{i})$ , so the level totals $n^{2} (lo g n - i)$ . Summing over $i = 0$ to $lo g n - 1$ gives $n^{2} \cdot \frac{l o g n ( l o g n + 1 )}{2}$ . The leaves add $n^{2}$ . The total is $Θ (n^{2} lo g^{2} n)$ .

PRACTICE 22 marks · MSQ

Let $f (n) = n^{1.5}$ and $g (n) = n lo g^{2} n$ . Which of the following statements are TRUE?

(A)
$f (n) = Ω (g (n))$
(B)
$f (n) = O (g (n))$
(C)
$g (n) = o (f (n))$
(D)
$f (n) = Θ (g (n))$

Answer and solution

Answer: (A), (C)

$\frac{f ( n )}{g ( n )} = \frac{n ^{1.5}}{n lo g ^{2} n} = \frac{n ^{0.5}}{lo g ^{2} n}$ .
Any positive power of $n$ dominates any power of $lo g n$ , so this ratio tends to $\infty$ .
Hence $f = ω (g)$ , and therefore $f = Ω (g)$ : A is TRUE.
$g (n) / f (n) \to 0$ , so $g = o (f)$ : C is TRUE.
$f = O (g)$ would need $f / g$ bounded above, which is false, so B is FALSE. $Θ$ needs both $O$ and $Ω$ , so D is FALSE.

PRACTICE 31 mark · NAT

The C fragment below is run with n = 20. How many times is the statement count++; executed?

int count = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        count++;
    }
}

Answer and solution

Answer: $210$

For each fixed $i$ , the inner loop runs exactly $i$ times, with $i$ going from 1 to $n$ .
Total $= \sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}$ .
At $n = 20$ : $\frac{20 \times 21}{2} = 210$ .

PRACTICE 41 mark · MCQ

What is the time complexity, in terms of $n$ , of the following recursive C function? Assume both recursive calls are executed exactly as written, with no compiler optimisation.

int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 1);
}

(A)
$Θ (n)$
(B)
$Θ (n lo g n)$
(C)
$Θ (2^{n})$
(D)
$Θ (n^{2})$

Answer and solution

Answer: (C)

Each call does $Θ (1)$ work besides its recursive calls, so the time is $Θ (number of calls)$ .
Let $C (n)$ be the number of calls made by f(n). Then $C (1) = 1$ and $C (n) = 1 + 2 C (n - 1)$ for $n \geq 2$ .
Unrolling gives $C (n) = 2^{n} - 1$ . For example, $C (5) = 31$ .
Hence the time is $Θ (2^{n})$ . Note that the stack depth, and so the auxiliary space, is only $Θ (n)$ .

PRACTICE 52 marks · NAT

$T (n) = 3 T (n /3) + n$ for $n$ a power of 3, with $T (1) = 1$ . If $T (n) = Θ (n^{c} lo g^{d} n)$ for constants $c$ and $d$ , what is $c + d$ ?

Answer and solution

Answer: $2$

$a = 3$ , $b = 3$ , so $n^{l o g_{b} a} = n^{l o g_{3} 3} = n$ .
$f (n) = n = Θ (n^{l o g_{b} a} lo g^{0} n)$ : Case 2 with $k = 0$ .
So $T (n) = Θ (n lo g n)$ . (Exactly, $T (n) = n lo g_{3} n + n$ .)
Hence $c = 1$ and $d = 1$ , so $c + d = 2$ .

PRACTICE 61 mark · NAT

The C fragment below is run with n = 1024. What is the final value of x?

int x = 0;
for (int i = 1; i <= n; i = i * 2) {
    for (int j = 1; j <= n; j++) {
        x++;
    }
}

Answer and solution

Answer: $11264$

The outer loop takes $i = 1, 2, 4, \dots, 1024$ , which is $2^{0}$ to $2^{10}$ : $⌊ lo g_{2} 1024 ⌋ + 1 = 11$ iterations, not 10.
The inner loop is independent of $i$ and runs $n = 1024$ times per outer iteration.
Total $= 11 \times 1024 = 11264$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Asymptotic worst case time and space complexity

Preparing in Kolkata? IAE Academy's course for GATE CSE.