Before writing a single data structure you need a way to say how fast and how much memory an algorithm uses without timing it on one particular computer. Asymptotic notation, loop analysis and recurrences are that language — every other topic in these notes ends with a line written in it.

Why analyse algorithms?

We count elementary operations (comparisons, assignments, arithmetic) rather than seconds, and we care about the order of growth — how the count scales when n doubles — not the exact number. Constants and lower-order terms are dropped: 3n² + 10n + 7 is simply O(n²).

Asymptotic notation: Big-O, Omega, Theta

Asymptotic analysis describes the growth of a function f(n) (the operation count) as n → ∞ by comparing it with a simpler function g(n). Three bounds are used:

f(n) = O(g(n)) ⇔ ∃ c > 0, n₀ : f(n) ≤ c · g(n) for all n ≥ n₀

Expression	Simplified	Why
`5n + 20`	`O(n)`	drop the constant factor 5 and the lower-order term 20
`n² + n log n`	`O(n²)`	`n log n` grows slower than `n²`
`2ⁿ + n¹⁰⁰`	`O(2ⁿ)`	any exponential eventually beats any polynomial
`log₂ n` vs `log₁₀ n`	both `O(log n)`	logarithms of different bases differ by a constant factor (`log₂ n = 3.32 · log₁₀ n`)
`n + m`	`O(n + m)`	two independent sizes stay in the answer — neither can be dropped
`100`	`O(1)`	constant — does not depend on `n` at all

Big-O growth table

The classes below cover almost every algorithm you will meet, from fastest to slowest. The right-hand column is the rule of thumb for coding interviews and contests: roughly 10⁸ simple operations run in about a second.

Class	Name	`n = 10`	`n = 100`	`n = 1000`	Largest `n` in ~1 s	Typical example
`O(1)`	constant	1	1	1	any	array index, hash lookup, push/pop
`O(log n)`	logarithmic	3	7	10	any	binary search, balanced BST operations
`O(√n)`	square root	3	10	32	`10¹⁶`	trial-division primality test
`O(n)`	linear	10	100	1 000	`10⁸`	linear search, one pass over an array
`O(n log n)`	linearithmic	33	664	9 966	`5·10⁶`	merge sort, heap sort, sorting then scanning
`O(n²)`	quadratic	100	10⁴	10⁶	`10⁴`	bubble/insertion sort, all pairs
`O(n³)`	cubic	1 000	10⁶	10⁹	`500`	naive matrix multiplication, Floyd–Warshall
`O(2ⁿ)`	exponential	1 024	1.3·10³⁰	10³⁰¹	`25`	all subsets, naive recursion with two branches
`O(n!)`	factorial	3.6·10⁶	9·10¹⁵⁷	—	`11`	all permutations, brute-force TSP

Order of growth, fastest to slowest

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
───────────────────────────────▶ slower growth, smaller feasible n

How to analyse a loop

Almost all non-recursive analysis reduces to one question per loop: how many times does the body run as a function of n? Then combine the loops with two rules.

Find the loop variable's path
Write down its start value, its stop condition and how it changes per iteration (+1, +k, ×2, squared…).
Solve for the iteration count
i = 0, 1, 2, … n−1 → n iterations. i = n, n−k, n−2k… → n/k. i = 1, 2, 4, 8 … n → log₂ n. i = 2, 2², 2⁴, 2⁸ … n → log log n.
Nested loops multiply
If the inner loop runs g(n) times for each of f(n) outer iterations, the total is f(n) · g(n). When the inner count depends on i, sum it: Σ i for i = 1..n is n(n+1)/2 = Θ(n²).
Sequential loops add
Loop A then loop B costs A + B; keep only the dominant term (n² + n = O(n²)), but keep both when sizes are independent (O(n + m)).
Charge the body
Multiply the iteration count by the cost of the body. A body that itself calls an O(log n) function inside an O(n) loop gives O(n log n).
Drop constants and lower-order terms
3n + 5 → O(n); n²/2 + n → O(n²). Keep the tightest class that remains.

Loop variable moves…	Example	Iterations	Class
by a constant (`+1`, `−1`)	`for i in range(n)`	`n`	`O(n)`
by a constant `k`	`while x >= b: x -= b`	`n / k`	`O(n)` — the `1/k` is a constant
multiplied / divided by `c`	`while x < n: x *= c`	`log_c n`	`O(log n)`
raised to a power `c`	`while x < n: x = x ** c`	`log log n`	`O(log log n)`
inner loop `0..n` for every outer `0..n`	`for i … for j …`	`n · n`	`O(n²)`
inner loop `i..n` (triangle)	`for i … for j in range(i, n)`	`n(n+1)/2`	`O(n²)` — half the square is still a square
inner loop doubles	`for i … j = 1; while j <= n: j *= 2`	`n · log n`	`O(n log n)`

Loop pattern: linear and fractional increments

The learner's original four examples are kept here, instrumented to print their iteration count so the complexity is visible. add decrements b by one per iteration, so it runs b times — O(b). subtract removes b from a per iteration, so it runs a / b times — still linear in a for a fixed b, because 1/b is a constant factor.

Python

def add(a, b):              # result += 1 while b counts down: O(b)
    result, steps = a, 0
    while b > 0:
        result += 1
        b -= 1
        steps += 1
    return result, steps

def subtract(a, b):         # how many times does b fit in a? O(a / b)
    count, steps = 0, 0
    while a >= b:
        a -= b
        count += 1
        steps += 1
    return count, steps

for a, b in [(5, 7), (5, 70)]:
    r, s = add(a, b)
    print(f"add({a}, {b}) = {r} after {s} iterations")
for a, b in [(100, 10), (1000, 10)]:
    r, s = subtract(a, b)
    print(f"subtract({a}, {b}) = {r} after {s} iterations")

C++

#include <iostream>
using namespace std;

int steps;                          // iteration counter shared by both functions

int add(int a, int b) {             // result += 1 while b counts down: O(b)
    int result = a;
    steps = 0;
    while (b > 0) { result++; b--; steps++; }
    return result;
}

int subtract(int a, int b) {        // how many times does b fit in a? O(a / b)
    int count = 0;
    steps = 0;
    while (a >= b) { a -= b; count++; steps++; }
    return count;
}

int main() {
    int adds[2][2] = {{5, 7}, {5, 70}};
    for (auto& ab : adds) {
        int r = add(ab[0], ab[1]);
        cout << "add(" << ab[0] << ", " << ab[1] << ") = " << r << " after " << steps << " iterations\n";
    }
    int subs[2][2] = {{100, 10}, {1000, 10}};
    for (auto& ab : subs) {
        int r = subtract(ab[0], ab[1]);
        cout << "subtract(" << ab[0] << ", " << ab[1] << ") = " << r << " after " << steps << " iterations\n";
    }
}

Java

public class Main {
    static int steps;                       // iteration counter shared by both functions

    static int add(int a, int b) {          // result += 1 while b counts down: O(b)
        int result = a;
        steps = 0;
        while (b > 0) { result++; b--; steps++; }
        return result;
    }

    static int subtract(int a, int b) {     // how many times does b fit in a? O(a / b)
        int count = 0;
        steps = 0;
        while (a >= b) { a -= b; count++; steps++; }
        return count;
    }

    public static void main(String[] args) {
        int[][] adds = {{5, 7}, {5, 70}};
        for (int[] ab : adds) {
            int r = add(ab[0], ab[1]);
            System.out.println("add(" + ab[0] + ", " + ab[1] + ") = " + r + " after " + steps + " iterations");
        }
        int[][] subs = {{100, 10}, {1000, 10}};
        for (int[] ab : subs) {
            int r = subtract(ab[0], ab[1]);
            System.out.println("subtract(" + ab[0] + ", " + ab[1] + ") = " + r + " after " + steps + " iterations");
        }
    }
}

JavaScript

function add(a, b) {                // result += 1 while b counts down: O(b)
    let result = a, steps = 0;
    while (b > 0) { result++; b--; steps++; }
    return [result, steps];
}

function subtract(a, b) {           // how many times does b fit in a? O(a / b)
    let count = 0, steps = 0;
    while (a >= b) { a -= b; count++; steps++; }
    return [count, steps];
}

for (const [a, b] of [[5, 7], [5, 70]]) {
    const [r, s] = add(a, b);
    console.log(`add(${a}, ${b}) = ${r} after ${s} iterations`);
}
for (const [a, b] of [[100, 10], [1000, 10]]) {
    const [r, s] = subtract(a, b);
    console.log(`subtract(${a}, ${b}) = ${r} after ${s} iterations`);
}

Output

add(5, 7) = 12 after 7 iterations
add(5, 70) = 75 after 70 iterations
subtract(100, 10) = 10 after 10 iterations
subtract(1000, 10) = 100 after 100 iterations

Time O(n) — n iterations, or n/k for a step of k · Space O(1)

Loop pattern: logarithmic and log-log scaling

When the loop variable is multiplied by a constant c each round, it reaches n after log_c n rounds — a thousandfold larger input adds only a handful of iterations. When the variable is raised to a power each round (2 → 4 → 16 → 256 → 65536), the exponent itself doubles, so the loop runs log log n times — practically constant.

Python

def multiply(n, c):          # result *= c until it reaches n: log_c(n) iterations
    result, steps = 1, 0
    while result < n:
        result *= c
        steps += 1
    return result, steps

def exponent(n, c):          # result = result ** c: the exponent doubles each time → log log n
    result, steps = 2, 0
    while result < n:
        result = result ** c
        steps += 1
    return result, steps

for n, c in [(1000, 10), (1024, 2), (1000000, 2)]:
    r, s = multiply(n, c)
    print(f"multiply({n}, {c}) = {r} after {s} iterations")
for n, c in [(65536, 2), (1000000000, 2)]:
    r, s = exponent(n, c)
    print(f"exponent({n}, {c}) = {r} after {s} iterations")

C++

#include <iostream>
using namespace std;

int steps;

long long multiply(long long n, long long c) {   // result *= c until it reaches n: log_c(n)
    long long result = 1;
    steps = 0;
    while (result < n) { result *= c; steps++; }
    return result;
}

long long ipow(long long base, long long e) {    // integer power for the log-log loop
    long long r = 1;
    for (long long i = 0; i < e; i++) r *= base;
    return r;
}

long long exponent(long long n, long long c) {   // result = result^c: exponent doubles → log log n
    long long result = 2;
    steps = 0;
    while (result < n) { result = ipow(result, c); steps++; }
    return result;
}

int main() {
    long long m[3][2] = {{1000, 10}, {1024, 2}, {1000000, 2}};
    for (auto& nc : m) {
        long long r = multiply(nc[0], nc[1]);
        cout << "multiply(" << nc[0] << ", " << nc[1] << ") = " << r << " after " << steps << " iterations\n";
    }
    long long e[2][2] = {{65536, 2}, {1000000000, 2}};
    for (auto& nc : e) {
        long long r = exponent(nc[0], nc[1]);
        cout << "exponent(" << nc[0] << ", " << nc[1] << ") = " << r << " after " << steps << " iterations\n";
    }
}

Java

public class Main {
    static int steps;

    static long multiply(long n, long c) {     // result *= c until it reaches n: log_c(n)
        long result = 1;
        steps = 0;
        while (result < n) { result *= c; steps++; }
        return result;
    }

    static long ipow(long base, long e) {      // integer power for the log-log loop
        long r = 1;
        for (long i = 0; i < e; i++) r *= base;
        return r;
    }

    static long exponent(long n, long c) {     // result = result^c: exponent doubles → log log n
        long result = 2;
        steps = 0;
        while (result < n) { result = ipow(result, c); steps++; }
        return result;
    }

    public static void main(String[] args) {
        long[][] m = {{1000, 10}, {1024, 2}, {1000000, 2}};
        for (long[] nc : m) {
            long r = multiply(nc[0], nc[1]);
            System.out.println("multiply(" + nc[0] + ", " + nc[1] + ") = " + r + " after " + steps + " iterations");
        }
        long[][] e = {{65536, 2}, {1000000000L, 2}};
        for (long[] nc : e) {
            long r = exponent(nc[0], nc[1]);
            System.out.println("exponent(" + nc[0] + ", " + nc[1] + ") = " + r + " after " + steps + " iterations");
        }
    }
}

JavaScript

function multiply(n, c) {        // result *= c until it reaches n: log_c(n) iterations
    let result = 1, steps = 0;
    while (result < n) { result *= c; steps++; }
    return [result, steps];
}

function exponent(n, c) {        // result = result ** c: exponent doubles each time → log log n
    let result = 2, steps = 0;
    while (result < n) { result = result ** c; steps++; }
    return [result, steps];
}

for (const [n, c] of [[1000, 10], [1024, 2], [1000000, 2]]) {
    const [r, s] = multiply(n, c);
    console.log(`multiply(${n}, ${c}) = ${r} after ${s} iterations`);
}
for (const [n, c] of [[65536, 2], [1000000000, 2]]) {
    const [r, s] = exponent(n, c);
    console.log(`exponent(${n}, ${c}) = ${r} after ${s} iterations`);
}

Output

multiply(1000, 10) = 1000 after 3 iterations
multiply(1024, 2) = 1024 after 10 iterations
multiply(1000000, 2) = 1048576 after 20 iterations
exponent(65536, 2) = 65536 after 4 iterations
exponent(1000000000, 2) = 4294967296 after 5 iterations

Time O(log n) for multiply, O(log log n) for exponent · Space O(1)

Loop pattern: nested and sequential loops

Nested loops multiply; loops one after another add. The program below counts the body executions of three classic nestings for n = 8 so you can match each count to its formula.

Python

n = 8

square = 0
for i in range(n):
    for j in range(n):           # inner runs n times for each of n outer → n²
        square += 1

triangle = 0
for i in range(n):
    for j in range(i, n):        # inner runs n-i times: n + (n-1) + … + 1 = n(n+1)/2
        triangle += 1

doubling = 0
for i in range(n):
    j = 1
    while j <= n:                # inner doubles: log2(n) + 1 rounds → n log n
        doubling += 1
        j *= 2

sequential = 0
for i in range(n):               # one loop then another: n + n = 2n → O(n)
    sequential += 1
for i in range(n):
    sequential += 1

print("n =", n)
print(f"square (i in 0..n, j in 0..n): {square} = n*n")
print(f"triangle (i in 0..n, j in i..n): {triangle} = n(n+1)/2")
print(f"doubling (i in 0..n, j = 1,2,4..n): {doubling} = n * (log2 n + 1)")
print(f"sequential (loop n then loop n): {sequential} = 2n")

C++

#include <iostream>
using namespace std;

int main() {
    int n = 8;

    int square = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) square++;          // n * n

    int triangle = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) triangle++;        // n + (n-1) + … + 1 = n(n+1)/2

    int doubling = 0;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= n; j *= 2) doubling++;    // inner doubles: log2(n) + 1 rounds

    int sequential = 0;
    for (int i = 0; i < n; i++) sequential++;          // n + n = 2n → O(n)
    for (int i = 0; i < n; i++) sequential++;

    cout << "n = " << n << "\n";
    cout << "square (i in 0..n, j in 0..n): " << square << " = n*n\n";
    cout << "triangle (i in 0..n, j in i..n): " << triangle << " = n(n+1)/2\n";
    cout << "doubling (i in 0..n, j = 1,2,4..n): " << doubling << " = n * (log2 n + 1)\n";
    cout << "sequential (loop n then loop n): " << sequential << " = 2n\n";
}

Java

public class Main {
    public static void main(String[] args) {
        int n = 8;

        int square = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) square++;          // n * n

        int triangle = 0;
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++) triangle++;        // n + (n-1) + … + 1 = n(n+1)/2

        int doubling = 0;
        for (int i = 0; i < n; i++)
            for (int j = 1; j <= n; j *= 2) doubling++;    // inner doubles: log2(n) + 1 rounds

        int sequential = 0;
        for (int i = 0; i < n; i++) sequential++;          // n + n = 2n → O(n)
        for (int i = 0; i < n; i++) sequential++;

        System.out.println("n = " + n);
        System.out.println("square (i in 0..n, j in 0..n): " + square + " = n*n");
        System.out.println("triangle (i in 0..n, j in i..n): " + triangle + " = n(n+1)/2");
        System.out.println("doubling (i in 0..n, j = 1,2,4..n): " + doubling + " = n * (log2 n + 1)");
        System.out.println("sequential (loop n then loop n): " + sequential + " = 2n");
    }
}

JavaScript

const n = 8;

let square = 0;
for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) square++;          // n * n

let triangle = 0;
for (let i = 0; i < n; i++)
    for (let j = i; j < n; j++) triangle++;        // n + (n-1) + … + 1 = n(n+1)/2

let doubling = 0;
for (let i = 0; i < n; i++)
    for (let j = 1; j <= n; j *= 2) doubling++;    // inner doubles: log2(n) + 1 rounds

let sequential = 0;
for (let i = 0; i < n; i++) sequential++;          // n + n = 2n → O(n)
for (let i = 0; i < n; i++) sequential++;

console.log("n =", n);
console.log(`square (i in 0..n, j in 0..n): ${square} = n*n`);
console.log(`triangle (i in 0..n, j in i..n): ${triangle} = n(n+1)/2`);
console.log(`doubling (i in 0..n, j = 1,2,4..n): ${doubling} = n * (log2 n + 1)`);
console.log(`sequential (loop n then loop n): ${sequential} = 2n`);

Output

n = 8
square (i in 0..n, j in 0..n): 64 = n*n
triangle (i in 0..n, j in i..n): 36 = n(n+1)/2
doubling (i in 0..n, j = 1,2,4..n): 32 = n * (log2 n + 1)
sequential (loop n then loop n): 16 = 2n

Time O(n²), O(n²), O(n log n), O(n) respectively · Space O(1)

Recurrence relations for recursive algorithms

A recursive algorithm's running time is defined in terms of itself: the cost of the current call plus the cost of the recursive calls it makes. Writing that down gives a recurrence relation; solving it gives the complexity.

Algorithm	Recurrence	What it says	Solution
Linear recursion (sum of `n` numbers, factorial)	`T(n) = T(n−1) + Θ(1)`	one call of size `n−1`, constant work	`Θ(n)`
Binary search	`T(n) = T(n/2) + Θ(1)`	one call on half the input	`Θ(log n)`
Merge sort	`T(n) = 2T(n/2) + Θ(n)`	two halves plus a linear merge	`Θ(n log n)`
Selection sort written recursively	`T(n) = T(n−1) + Θ(n)`	one smaller call plus a linear scan	`Θ(n²)`
Tower of Hanoi	`T(n) = 2T(n−1) + Θ(1)`	two calls on `n−1` discs	`Θ(2ⁿ)`
Naive Fibonacci	`T(n) = T(n−1) + T(n−2) + Θ(1)`	two calls, barely smaller	`Θ(φⁿ) ≈ Θ(1.618ⁿ)`
Strassen matrix multiply	`T(n) = 7T(n/2) + Θ(n²)`	seven half-size products	`Θ(n^log₂7) ≈ Θ(n^2.81)`

Three methods solve a recurrence:

Recursion tree: why merge sort is n log n

For T(n) = 2T(n/2) + n every level of the tree does n work in total — the input is split in half but there are twice as many pieces. There are log₂ n levels of splitting plus the leaves, so the total is n · (log₂ n + 1) = Θ(n log n).

Recursion tree of T(n) = 2T(n/2) + n

level 0:                 n                       work: n
                      /     \
level 1:          n/2         n/2                work: 2 · n/2  = n
                 /   \       /   \
level 2:       n/4   n/4   n/4   n/4             work: 4 · n/4  = n
                …     …     …     …
level log n:   1  1  1  1  1  1  1  1   (n leaves)  work: n · 1 = n
                                                  ─────────────────
                                      total: n · (log₂ n + 1) = Θ(n log n)

The program below evaluates that recurrence exactly for powers of two and prints the total next to the closed form — the two columns agree at every size.

Python

def T(n):                        # T(n) = 2 T(n/2) + n, T(1) = 1
    if n == 1:
        return 1
    return 2 * T(n // 2) + n

def closed(n):                   # n * (log2 n + 1)
    log2 = 0
    while (1 << log2) < n:
        log2 += 1
    return n * (log2 + 1)

for n in [1, 2, 4, 8, 16, 1024]:
    print(f"n = {n}: T(n) = {T(n)}, n*(log2 n + 1) = {closed(n)}")

C++

#include <iostream>
using namespace std;

long long T(long long n) {               // T(n) = 2 T(n/2) + n, T(1) = 1
    if (n == 1) return 1;
    return 2 * T(n / 2) + n;
}

long long closed(long long n) {          // n * (log2 n + 1)
    int log2 = 0;
    while ((1LL << log2) < n) log2++;
    return n * (log2 + 1);
}

int main() {
    for (long long n : {1, 2, 4, 8, 16, 1024})
        cout << "n = " << n << ": T(n) = " << T(n) << ", n*(log2 n + 1) = " << closed(n) << "\n";
}

Java

public class Main {
    static long T(long n) {                  // T(n) = 2 T(n/2) + n, T(1) = 1
        if (n == 1) return 1;
        return 2 * T(n / 2) + n;
    }

    static long closed(long n) {             // n * (log2 n + 1)
        int log2 = 0;
        while ((1L << log2) < n) log2++;
        return n * (log2 + 1);
    }

    public static void main(String[] args) {
        for (long n : new long[]{1, 2, 4, 8, 16, 1024})
            System.out.println("n = " + n + ": T(n) = " + T(n) + ", n*(log2 n + 1) = " + closed(n));
    }
}

JavaScript

function T(n) {                          // T(n) = 2 T(n/2) + n, T(1) = 1
    if (n === 1) return 1;
    return 2 * T(Math.floor(n / 2)) + n;
}

function closed(n) {                     // n * (log2 n + 1)
    let log2 = 0;
    while ((1 << log2) < n) log2++;
    return n * (log2 + 1);
}

for (const n of [1, 2, 4, 8, 16, 1024])
    console.log(`n = ${n}: T(n) = ${T(n)}, n*(log2 n + 1) = ${closed(n)}`);

Output

n = 1: T(n) = 1, n*(log2 n + 1) = 1
n = 2: T(n) = 4, n*(log2 n + 1) = 4
n = 4: T(n) = 12, n*(log2 n + 1) = 12
n = 8: T(n) = 32, n*(log2 n + 1) = 32
n = 16: T(n) = 80, n*(log2 n + 1) = 80
n = 1024: T(n) = 11264, n*(log2 n + 1) = 11264

Time Θ(n log n) — the recurrence's solution · Space O(log n) recursion depth

Master theorem

For divide-and-conquer recurrences of the form T(n) = a·T(n/b) + f(n) with a ≥ 1 subproblems each of size n/b (b > 1), the answer depends on which wins: the leaves (n^(log_b a) of them, each Θ(1)) or the root's work f(n).

T(n) = a · T(n / b) + f(n) — compare f(n) with n^(log_b a)

Case	Condition	Meaning	Result
1 — leaves dominate	`f(n) = O(n^(log_b a − ε))` for some `ε > 0`	`f(n)` is polynomially smaller than `n^(log_b a)`	`T(n) = Θ(n^(log_b a))`
2 — balanced	`f(n) = Θ(n^(log_b a))`	every level does the same work; there are `log n` levels	`T(n) = Θ(n^(log_b a) · log n)`
3 — root dominates	`f(n) = Ω(n^(log_b a + ε))` and `a·f(n/b) ≤ c·f(n)` for some `c < 1`	`f(n)` is polynomially larger; the top call does most of the work	`T(n) = Θ(f(n))`

Recurrence	`a`, `b`	`n^(log_b a)`	`f(n)`	Case	Solution
`T(n) = 2T(n/2) + n` (merge sort)	2, 2	`n¹`	`n`	2	`Θ(n log n)`
`T(n) = T(n/2) + 1` (binary search)	1, 2	`n⁰ = 1`	`1`	2	`Θ(log n)`
`T(n) = 4T(n/2) + n`	4, 2	`n²`	`n`	1	`Θ(n²)`
`T(n) = 8T(n/2) + n²` (naive matrix multiply)	8, 2	`n³`	`n²`	1	`Θ(n³)`
`T(n) = 7T(n/2) + n²` (Strassen)	7, 2	`n^2.81`	`n²`	1	`Θ(n^log₂7)`
`T(n) = 2T(n/2) + n²`	2, 2	`n`	`n²`	3	`Θ(n²)`
`T(n) = T(n/2) + n`	1, 2	`1`	`n`	3	`Θ(n)`
`T(n) = 2T(n/2) + n log n`	2, 2	`n`	`n log n`	none — not polynomially larger	`Θ(n log² n)` (extended form)

Identify a, b, f(n)
a = number of recursive calls, b = the factor the input shrinks by, f(n) = the work done outside the calls (splitting, merging, scanning).
Compute the critical exponent
p = log_b a. Examples: a = 2, b = 2 → p = 1; a = 4, b = 2 → p = 2; a = 1, b = 2 → p = 0.
Compare f(n) with n^p
Smaller by a polynomial factor → case 1. Equal → case 2. Larger by a polynomial factor → case 3 (check regularity).
Read off T(n)
Θ(n^p), Θ(n^p log n) or Θ(f(n)).

Space complexity vs auxiliary space

Term	What is counted	Example: sum an array of `n` numbers iteratively
Space complexity	all memory the algorithm needs — the input itself plus any extra	`O(n)` — the array has to be there
Auxiliary space	only the extra memory beyond the input: temporaries, new arrays, hash maps, the recursion stack	`O(1)` — one accumulator

Interviewers nearly always mean auxiliary space when they ask “what is the space complexity?”, because it is what distinguishes solutions: sorting in place is O(1) auxiliary, merge sort's buffer is O(n), and a recursive solution pays for its call stack. Recursion is the classic hidden cost — each pending call keeps a frame alive until it returns.

Python

depth = 0
max_depth = 0

def add_recursion(n):            # each pending call holds a frame: O(n) auxiliary space
    global depth, max_depth
    depth += 1
    max_depth = max(max_depth, depth)
    result = 0 if n <= 0 else n + add_recursion(n - 1)
    depth -= 1
    return result

def add_iterative(n):            # a counter and an accumulator: O(1) auxiliary space
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

for n in (5, 50):
    max_depth = 0
    print(f"add_recursion({n}) = {add_recursion(n)}, max depth = {max_depth}")
print(f"add_iterative(50) = {add_iterative(50)}, extra variables = 2")

C++

#include <iostream>
#include <algorithm>
using namespace std;

int depth = 0, maxDepth = 0;

int addRecursion(int n) {            // each pending call holds a frame: O(n) auxiliary space
    depth++;
    maxDepth = max(maxDepth, depth);
    int result = n <= 0 ? 0 : n + addRecursion(n - 1);
    depth--;
    return result;
}

int addIterative(int n) {            // a counter and an accumulator: O(1) auxiliary space
    int total = 0;
    for (int i = 1; i <= n; i++) total += i;
    return total;
}

int main() {
    for (int n : {5, 50}) {
        maxDepth = 0;
        int r = addRecursion(n);
        cout << "add_recursion(" << n << ") = " << r << ", max depth = " << maxDepth << "\n";
    }
    cout << "add_iterative(50) = " << addIterative(50) << ", extra variables = 2\n";
}

Java

public class Main {
    static int depth = 0, maxDepth = 0;

    static int addRecursion(int n) {         // each pending call holds a frame: O(n) auxiliary space
        depth++;
        maxDepth = Math.max(maxDepth, depth);
        int result = n <= 0 ? 0 : n + addRecursion(n - 1);
        depth--;
        return result;
    }

    static int addIterative(int n) {         // a counter and an accumulator: O(1) auxiliary space
        int total = 0;
        for (int i = 1; i <= n; i++) total += i;
        return total;
    }

    public static void main(String[] args) {
        for (int n : new int[]{5, 50}) {
            maxDepth = 0;
            int r = addRecursion(n);
            System.out.println("add_recursion(" + n + ") = " + r + ", max depth = " + maxDepth);
        }
        System.out.println("add_iterative(50) = " + addIterative(50) + ", extra variables = 2");
    }
}

JavaScript

let depth = 0, maxDepth = 0;

function addRecursion(n) {           // each pending call holds a frame: O(n) auxiliary space
    depth++;
    maxDepth = Math.max(maxDepth, depth);
    const result = n <= 0 ? 0 : n + addRecursion(n - 1);
    depth--;
    return result;
}

function addIterative(n) {           // a counter and an accumulator: O(1) auxiliary space
    let total = 0;
    for (let i = 1; i <= n; i++) total += i;
    return total;
}

for (const n of [5, 50]) {
    maxDepth = 0;
    const r = addRecursion(n);
    console.log(`add_recursion(${n}) = ${r}, max depth = ${maxDepth}`);
}
console.log(`add_iterative(50) = ${addIterative(50)}, extra variables = 2`);

Output

add_recursion(5) = 15, max depth = 6
add_recursion(50) = 1275, max depth = 51
add_iterative(50) = 1275, extra variables = 2

Time O(n) time for both · Space O(n) auxiliary (recursive) vs O(1) (iterative)

Interview Q&A

What is the difference between Big-O, Big-Omega and Big-Theta?

Why do we ignore constants and lower-order terms?

Can an O(n²) algorithm be faster than an O(n log n) one?

How do you find the time complexity of nested loops?

What is the master theorem and when can you not use it?

What is the difference between space complexity and auxiliary space?

What is amortised analysis?