Data structures · 3 lessons

FoundationsHow we measure cost

Before any data structure or algorithm, get three tools in place: Big-O to describe cost, recursion to think with, and amortised analysis to explain why something is "fast on average". Every complexity figure elsewhere on the site builds on these.

Why learn Foundations

Where it shows up

Why it was fast in testing and times out in production

Go from 100 rows to a million — ten thousand times the data — and an O(n²) program does a hundred million times the work, while O(n log n) does about thirty thousand times. Big-O lets you predict that before you write the code.

→ Lesson: Big-O Notation

Why pushing to a dynamic array counts as O(1)

When the array fills up it has to move, and that one push is O(n) — but averaged out, each push is still constant time. Amortised analysis is how you talk about "occasionally slow, fast overall".

→ Lesson: Amortized Analysis

Handing the problem to a smaller version of yourself

Folders contain folders; expressions contain expressions. Recursion lets you describe one layer and leave the rest to the same function. Trees, DFS, divide and conquer and DP are all built on it.

→ Lesson: Recursion

Lessons

3 lessons

#AlgorithmComplexityDifficultyStatus

01Big-O Notation Time and space complexityDescribing how cost grows with the input size nUsed for: Judging whether code will hold up under real data; asked in every interview—Space —available 02Recursion RecursionA function calling itself, with the call stack remembering the way backUsed for: Tree traversal, DFS, divide and conquer, and where DP startsDepends on the recursion treeSpace O(depth)available 03Amortized Analysis Amortised analysisThe average cost over a run of operations, not the worst single oneUsed for: Why dynamic arrays, hash table growth and union-find are fast enough—Space —available