Complexity formulas

Asymptotic complexity and recurrences. 14 formulas for GATE CS, DA Data Structures and Algorithms, each with when to use it. Each is explained in the topic notes.

All 14 Complexity formulas

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.

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 $Θ$ .

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}$ .

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.

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 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.

Where this was asked: 2020 (1), 2022 (2), 2023 (2), 2024 (3), 2025 (2), 2026 (4). See the 14 previous-year questions on Complexity. This shows what was asked, not what will be asked.

KEEP GOING

Complexity: the notes and 14 solved previous-year questions