Complexity Analysis

How to measure and compare algorithm efficiency using Big O notation.

Why Complexity Matters

Imagine you have two algorithms that solve the same problem. How do you decide which one is better? You could run them and measure the time—but that depends on your computer's speed, the input size, and many other factors.

Complexity analysis gives us a way to compare algorithms independent of hardware. It describes how an algorithm's resource usage grows as the input size increases.

⚡ Key insight: The difference between O(n) and O(n²) can mean the difference between 1 second and 11 days for processing 1 million items!

Big O Notation

Big O notation describes the upper bound of an algorithm's growth rate. It focuses on the dominant term and ignores constants.

📐 What Big O Tells Us

• O(1) — Constant: Same time regardless of input size
• O(log n) — Logarithmic: Halves the problem each step
• O(n) — Linear: Time grows proportionally with input
• O(n log n) — Linearithmic: Efficient sorting algorithms
• O(n²) — Quadratic: Nested loops over the input
• O(2ⁿ) — Exponential: Doubles with each additional element

Time Complexity

Time complexity measures how the running time of an algorithm changes with input size.

O(1)

Constant Time

The algorithm takes the same time regardless of input size.

// Accessing array element by index
function getFirst(arr) {
    return arr[0];  // Always one operation
}

// Hash table lookup
const value = hashMap.get("key");  // O(1) average

O(log n)

Logarithmic Time

The algorithm halves the problem size with each step. Very efficient!

// Binary search - find target in sorted array
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

O(n)

Linear Time

Time grows proportionally with input size. Must look at each element once.

// Find maximum value in array
function findMax(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

O(n²)

Quadratic Time

Nested loops over the input. Gets slow very quickly for large inputs!

// Bubble sort - compare every pair
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

Complexity Comparison

How long does each complexity take for different input sizes? (assuming 1 operation = 1 microsecond)

Complexity	n = 10	n = 100	n = 1,000	n = 10,000
O(1)	1 μs	1 μs	1 μs	1 μs
O(log n)	3 μs	7 μs	10 μs	13 μs
O(n)	10 μs	100 μs	1 ms	10 ms
O(n log n)	33 μs	664 μs	10 ms	132 ms
O(n²)	100 μs	10 ms	1 sec	1.6 min
O(2ⁿ)	1 ms	10²² years	∞	∞

Space Complexity

Space complexity measures how much additional memory an algorithm needs as input size grows.

O(1) Space

Uses a fixed amount of extra memory (e.g., a few variables)

sum = a + b

O(n) Space

Memory grows with input size (e.g., copying an array)

copy = [...arr]

💡 Trade-off: Sometimes you can trade space for time. For example, caching results (memoization) uses more memory but avoids recalculating values.

Quick Analysis Tips

1️⃣

Count the loops

One loop = O(n), nested loops = O(n²), triple nested = O(n³)

2️⃣

Drop constants

O(2n) = O(n), O(n + 100) = O(n)

3️⃣

Keep only dominant term

O(n² + n) = O(n²), O(n + log n) = O(n)

4️⃣

Halving = logarithmic

If the problem size halves each step → O(log n)

Content adapted from Hello 算法 - Complexity Analysis by Krahets, licensed under CC BY-NC-SA 4.0.