Time Complexity (Big O basics)

"Big O is not about how fast your code runs on your laptop — it's about how the runtime grows as the input gets bigger."

Part 1: What is Big O?

Imagine you have an array of 10 items. Your algorithm takes 10 steps. Now the array has 1,000,000 items. How many steps does it take? Big O answers that question. It describes the worst-case growth rate — how the number of operations scales relative to the input size n.

Why it matters in DSA

javascript

// Array of 1,000,000 items
// O(n)    → ~1,000,000 operations  ← acceptable
// O(n²)   → ~1,000,000,000,000 operations  ← too slow
// O(log n) → ~20 operations  ← blazing fast

// Interviewers care about Big O, not milliseconds.

Drop constants and non-dominant terms

javascript

// Big O ignores constants:
// O(2n)     → O(n)
// O(3n + 5) → O(n)
// O(n² + n) → O(n²)  ← n² dominates as n grows

// You only keep the term that grows the fastest.

Part 2: The Big O Classes

O(1) — Constant

Always the same number of steps, no matter how big the input.

javascript

function getFirst(arr) {
    return arr[0]; // one operation
}
// n=10 → 1 step
// n=1M → 1 step

O(log n) — Logarithmic

Halves the problem each step. Binary search is the classic example.

javascript

// Binary search on sorted array
function binarySearch(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        let mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
// n=1M → ~20 steps!

O(n) — Linear

One loop through the input. Scales directly with size.

javascript

function findMax(arr) {
    let max = arr[0];
    for (let x of arr) {
        if (x > max) max = x;
    }
    return max;
}
// n=1M → 1M steps

O(n log n) — Linearithmic

Efficient sorting algorithms like Merge Sort and Quick Sort.

javascript

// Built-in sort is O(n log n)
arr.sort((a, b) => a - b);
// n=1M → ~20M steps (manageable)

O(n²) — Quadratic

Nested loops — each element is compared with every other. Gets slow fast.

javascript

// Bubble sort — O(n²)
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        // n × n = n² operations
    }
}
// n=1000 → 1,000,000 steps

O(2ⁿ) — Exponential

Doubles with each added element. Only feasible for very small inputs.

javascript

// Naive Fibonacci — O(2ⁿ)
function fib(n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}
// n=40 → ~1 billion calls!

Part 3: Space Complexity

Space complexity measures how much extra memory your algorithm uses as the input grows — same Big O notation, different resource.

O(1) space — no extra memory

javascript

function sum(arr) {
    let total = 0;         // only one extra variable
    for (let x of arr) total += x;
    return total;
}
// No matter how big arr is, we only use one extra variable → O(1) space

O(n) space — grows with input

javascript

function copyArray(arr) {
    let result = [];       // new array same size as input
    for (let x of arr) result.push(x);
    return result;
}
// result grows with arr → O(n) space

Reading complexity in an interview

javascript

// How to analyze time complexity quickly:

// 1 loop                → O(n)
// 2 nested loops         → O(n²)
// Halving each step      → O(log n)
// Loop + binary search   → O(n log n)
// Recursive tree (no memo) → O(2ⁿ)
// HashMap lookup         → O(1)

// When asked "what's the complexity?"
// → Count the loops and how input shrinks/grows.