Time & Space Complexity

Before you write a single line of "real" DSA, you need a way to *talk about how fast code is*. That language is Big O. Once it clicks, you can read a problem's constraints and instantly know what kinds of solutions can possibly fit. This page builds that intuition from scratch and finishes at interview-grade fluency.

What Big O Actually Says

Big O is a *growth rate*: as the input n gets bigger, how does the number of operations grow?

It is not "seconds" or "milliseconds". It's a shape — flat, linear, quadratic, exponential.

Card-sorting analogy: 10 cards sort fast no matter the method. 10,000 cards reveal the difference between a method that grows linearly and one that grows quadratically. Big O is the language for that difference.

Formal version (one line): f(n) = O(g(n)) if there exist constants c, nâ‚€ such that f(n) ≤ c·g(n) for all n ≥ n₀. In plain English: ignore small inputs, ignore constant factors, just look at the shape.

The Common Complexities (Memorise These)

From fastest to slowest:

Big O	Name	Looks like	Typical example
O(1)	constant	one step	array index, hash lookup, push/pop
O(log n)	logarithmic	input halves each step	binary search, balanced BST
O(n)	linear	one pass	linear search, sum of an array
O(n log n)	linearithmic	divide + linear merge	merge sort, heap sort
O(n²)	quadratic	nested loops	bubble/selection/insertion sort
O(2ⁿ)	exponential	doubling tree	naive recursive Fibonacci, all subsets
O(n!)	factorial	all orderings	brute-force TSP, all permutations

A useful number to remember: about 10⁸ simple operations per second. So:

• n = 10⁵ and O(n²) → 10¹⁰ ops → way too slow.
• n = 10⁵ and O(n log n) → ~2 × 10⁶ ops → instant.

This is *why* the language matters: you can rule out whole approaches just by looking at the input size.

Counting Operations — A Worked Example

`js function maxPairSum(arr) { // n = arr.length let best = -Infinity; // 1 for (let i = 0; i < arr.length; i++) { // n times for (let j = i + 1; j < arr.length; j++) { // up to n-1 times best = Math.max(best, arr[i] + arr[j]); // O(1) } } return best; // 1 } `

Inner loop runs (n-1) + (n-2) + ... + 0 = n(n-1)/2 times. Drop the constants and lower-order terms → O(n²).

Beginner Mistakes to Skip

1. Treating .includes() / indexOf() as O(1). They're O(n). A "single" call inside a loop usually means O(n²). 2. Counting input itself as the work. If you read n numbers, that's already O(n) — don't claim O(1). 3. Counting the constant +1. O(n+1), O(2n), O(n+5) all simplify to O(n). Drop constants. 4. Mixing up worst, average, best. Quicksort is O(n log n) *average*, O(n²) *worst*. Always say which. 5. Forgetting the call stack. Recursion uses memory too. Recursing n deep = O(n) extra space, even if you allocate nothing else. 6. String concat in a loop (s += "x"). Often O(n²) because strings are immutable; use an array + join.

Intermediate: Big O vs Big Theta vs Big Omega

Notation	Meaning	When you'd say it
O(g(n))	upper bound	"won't be worse than g(n)"
Ω(g(n))	lower bound	"won't be better than g(n)"
Θ(g(n))	tight bound	"grows exactly like g(n)"

In casual interview talk, "O(n)" usually means Θ(n). It's technically correct but sloppy to call something O(n²) when you can say O(n). Always state the *tightest* bound you can prove.

Intermediate: Loop Patterns → Complexity

`js // O(n) — one pass for (let i = 0; i < n; i++) work();

// O(n²) — two independent loops over n for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) work();

// O(n²) — triangular: n + (n-1) + ... + 1 = n(n+1)/2 for (let i = 0; i < n; i++) for (let j = i; j < n; j++) work();

// O(log n) — input halves each step for (let i = n; i > 0; i = Math.floor(i / 2)) work();

// O(n log n) — outer n × inner log n for (let i = 0; i < n; i++) for (let j = 1; j < n; j *= 2) work(); `

Recognise these in your sleep. They're the building blocks of almost every algorithm.

Intermediate: Space Complexity

Two parts:

• Auxiliary space: extra memory beyond the input — the only thing interviewers usually care about.
• Stack space: memory used by recursive call frames. factorial(n) has O(n) stack space, even though it allocates nothing else.

In-place algorithms (e.g., quicksort partitioning) are often described as O(1) auxiliary, but they still use O(log n) stack space because of recursion. Be precise: "O(1) extra memory, O(log n) stack".

Intermediate: Recurrences (Master Theorem Lite)

For divide-and-conquer recurrences T(n) = a·T(n/b) + O(nᵈ):

Compare	Result
d > log_b a	T(n) = O(nᵈ)
d = log_b a	T(n) = O(nᵈ log n)
d < log_b a	T(n) = O(n^(log_b a))

Examples:

• Merge sort: T(n) = 2T(n/2) + O(n) → a=2, b=2, d=1, equal → O(n log n).
• Binary search: T(n) = T(n/2) + O(1) → a=1, b=2, d=0, equal → O(log n).
• Karatsuba multiplication: T(n) = 3T(n/2) + O(n) → d < logâ‚‚ 3 ≈ 1.58 → O(n^1.58).

You don't need to derive it on the spot — just recognise the standard ones.

Advanced: Amortised Analysis

A few expensive operations *spread* across many cheap ones; the average per operation is what matters.

• Dynamic array push (Python list, Java ArrayList, JS array): most pushes are O(1), but every so often the array doubles in size — that resize copies all elements, O(n). Because doublings get exponentially rare, the *amortised* cost per push is O(1).
• Hash table insert: O(1) average; an occasional rehash is O(n), still amortised O(1).
• Splay tree / Fibonacci heap operations: individual ops can be slow, but the sequence is bounded.

Interviewers love asking why array.push is "O(1) amortised". Now you know.

Advanced: Constraint → Algorithm Cheatsheet

Read the input limits *first*. They tell you what's allowed:

n	Max feasible complexity	What it usually means
≤ 10	O(n!), O(2ⁿ)	brute force, permutations, backtracking
≤ 25	O(2ⁿ)	bitmask DP, subset enumeration
≤ 100	O(n³) / O(n⁴)	Floyd–Warshall, multi-loop DP
≤ 1,000	O(n²)	DP grid, two-loop scan
≤ 10⁵	O(n log n)	sort + sweep, segment trees, binary search
≤ 10⁶	O(n)	hash maps, two pointers, sliding window
≤ 10⁹	O(log n) / O(√n)	math, binary search on the answer

When you see n ≤ 10⁵, your brain should auto-think "O(n log n) target".

Advanced: Common Mistakes Even Pros Make

1. Hidden cost of "in-place" maps. Mutating a structure inside a loop where every mutation is O(n) (e.g., arr.unshift in JS) blows up to O(n²). 2. Sorting inside a loop. Sort n items inside a loop that runs n times → O(n² log n). Sort once outside. 3. Calling Object.keys(...).length or recomputing a derived value each iteration → O(n²) by accident. 4. Forgetting that string slicing copies. s.slice(...) is O(length). Doing it in a loop is often O(n²). 5. Cache misses ≠ Big O, but matter. A "slower" O(n) array beats a "faster" O(n) linked list because of cache locality. Big O is necessary, not sufficient. 6. Average vs amortised vs expected. Three different ideas; learn to use them precisely.

Advanced: Talking About Complexity in Interviews

A short script that always works:

> "Time is O(?) because [count the dominant work]. Space is O(?) because [count the extra structures + the recursion depth]. Worst case is [...]; average is [...]; the input constraints suggest we want O(?), so this fits."

Bonus: explicitly call out the trade-offs ("we trade O(n) extra space for O(n) time instead of O(n²) time with O(1) space"). Hiring signal: huge.

Advanced: Beyond Big O

• Cache-aware analysis — algorithms that respect cache lines (e.g., block matrix multiply) can be 10–100× faster than naive ones with the same Big O.
• Parallel complexity (PRAM) — work + depth model for parallel algorithms.
• Lower bounds — comparison sort cannot do better than Ω(n log n); some problems are *provably* hard (P vs NP).
• Approximation algorithms — when exact solutions are exponential, accept "within 2× of optimal" in polynomial time.

You don't need these on day one, but knowing they exist explains why senior engineers don't worship Big O blindly.

Practice Path

1. Stare at 10 random snippets and shout the Big O before reading the rest. Speed = fluency. 2. Take a brute-force O(n²) and reduce it to O(n) using a hash map (e.g., Two Sum). Explain *what work disappeared*. 3. Solve the same problem with input n = 10⁵ first using a list and indexOf, then a Set. Time both. Feel the constant factor *and* the Big O. 4. Pick any recursive function and write its recurrence T(n) = ...; classify it via the master theorem.