Module 0 · Foundations
Module 0 is the part of the course that does not teach you a single algorithm. It teaches the five things every algorithm lesson after it will assume you can already do: measure cost, reason about recursion, picture memory, know your language's built-ins and work a problem methodically. Skipping it is the most common reason people stall at Module 3.
This is the first module of DSA: Zero to Mastery. If you have not read the course map yet, start with How to Use This Course; it is also the first lesson here. The wider Algorithms section has the older overview pages that this course expands.
What the module covers
Seven lessons and a capstone, roughly five and a half hours of reading plus the exercises.
| # | Lesson | After it you will be able to… | Minutes |
|---|---|---|---|
| 0.1 | How to Use This Course & Study Plan Overview | Pick a study plan, read a lesson the way it is meant to be read, keep a problem log and track progress. | 15 |
| 0.2 | Complexity Analysis: Big-O, Amortized Analysis & Recurrences | Derive the time and space cost of any loop, recursion or data-structure operation, prove it with witness constants, solve recurrences with the Master theorem and argue amortized bounds three ways. | 60 |
| 0.3 | Recursion & Mathematical Induction | Write a recursive function with a correct base case and progress measure, prove it by induction, convert it to iteration, and prove a loop with an invariant. | 50 |
| 0.4 | How Data Structures Live in Memory | Explain why two O(n) algorithms can differ 50× in wall time: cache lines, pointer chasing, allocation, and the layout of arrays, lists and hash tables. | 45 |
| 0.5 | Your Language's Data Structures: Python, Java, C++, JavaScript | State the real complexity of every built-in operation you call: list append, dict lookup, string slicing, ArrayList.remove, std::map, Array.prototype.shift. | 55 |
| 0.6 | How to Solve Any Problem: The Method | Run a repeatable procedure from clarifying the statement to testing the code, and know what to do when stuck. | 40 |
| 0.7 | Testing & Debugging Algorithms | Build an edge-case checklist, write a brute-force comparator and a randomized stress test, and localise a bug by shrinking the failing input. | 40 |
| 0.8 | Capstone: Benchmark Your Language | Measure your language's array, hash map and sorted structure against each other, predict the curves from Big-O and cache behaviour, and explain every surprise. | 120 |
Why this order
The lessons depend on each other more than their titles suggest.
flowchart TD
A["0.1 How to use<br/>this course"] --> B["0.2 Complexity<br/>analysis"]
B --> C["0.3 Recursion &<br/>induction"]
B --> D["0.4 Data structures<br/>in memory"]
D --> E["0.5 Your language's<br/>data structures"]
C --> F["0.6 How to solve<br/>any problem"]
E --> F
F --> G["0.7 Testing &<br/>debugging"]
E --> H["0.8 Capstone:<br/>benchmark your language"]
G --> H
B --> H
Complexity first because every other lesson states a cost, and a cost you cannot derive is a cost you will misremember. The lesson goes further than the usual Big-O cheat sheet: it covers amortized analysis (so dynamic arrays and hash tables make sense in Module 1) and recurrences (so merge sort, binary search and divide and conquer make sense in Module 2 and Module 5).
Recursion second because trees, graphs, backtracking and dynamic programming are all recursion wearing different clothes, and because induction is the proof technique behind nearly every correctness argument in the course. The lesson pairs each recursive pattern with the proof that it works.
Memory third because Big-O says a linked list and an array both scan in O(n), and a real machine says the linked list is slower by a factor that depends on whether its nodes are contiguous. The lesson explains cache lines, pointer chasing and allocation; the complexity lesson leans on it for its "constants matter" section.
Your language fourth because interview and production code is written in a real language whose built-ins have real costs. Python's list.pop(0) is O(n). Java's LinkedList.get(i) is O(i). JavaScript's Array.prototype.shift is O(n) in most engines. Knowing these is the difference between an O(n) design and an accidental O(n²) implementation.
Method and testing last because they are habits, and habits are easier to form once you have something concrete to apply them to. The method lesson gives you a procedure; the testing lesson gives you the tools to find out whether the procedure produced a correct answer.
The capstone closes the loop: you predict from theory, measure on your machine, and reconcile the difference.
Prerequisites
You can write loops, functions and classes in at least one of Python, Java, C++ or JavaScript/TypeScript, and you know what an array, a string and a hash map are at the level of using them. You do not need calculus; the complexity lesson uses logarithms and sums, and it derives the ones it needs. If any of this is shaky, CS Fundamentals covers how a computer executes code, and How Computers Work is the single most useful page to read before 0.4.
How to study this module
Module 0 is read-heavy by design; the practice ladders are shorter than in later modules and lean towards analysis exercises. Three rules make it stick.
- Do the derivations on paper. When the complexity lesson analyses a nested loop or solves a recurrence, cover the answer and derive it yourself first. The skill being trained is derivation, not recognition.
- Run every code block in your language. Each lesson's code group has a self-checking
main. Change the inputs. Break the asserts on purpose and see what fails. For the recursion lesson, step through one recursive call in a debugger and watch the stack grow. - Start the problem log now. Lesson 0.1 gives the template. Every problem you touch in the course, including the small analysis exercises here, gets a row. By Module 11 that log is your revision plan.
Tick a lesson in the sidebar when you finish it, or press Mark lesson done & continue at the bottom of the page. The module progress bar fills as you go and feeds the course bar on the course map.
Where this module feeds
Nothing here is used once and discarded. The map below shows which later module pulls on which foundation lesson most heavily.
flowchart LR
CX["0.2 Complexity"] --> M1["Module 1<br/>Linear structures"]
CX --> M2["Module 2<br/>Searching & sorting"]
RC["0.3 Recursion"] --> M3["Module 3<br/>Trees"]
RC --> M5["Module 5<br/>Paradigms"]
RC --> M6["Module 6<br/>Dynamic programming"]
MEM["0.4 Memory"] --> M1
MEM --> M9["Module 9<br/>Cache-efficient algorithms"]
LANG["0.5 Your language"] --> M11["Module 11<br/>Interview mastery"]
MTH["0.6 Method"] --> M11
TST["0.7 Testing"] --> M12["Module 12<br/>Competitive programming"]
The complexity lesson is cited by essentially every page in the course; the recursion lesson by every tree, graph, backtracking and DP page; the memory lesson by every page that compares an array-based structure with a pointer-based one. Expect to come back here.
Start
Begin with How to Use This Course & Study Plan Overview, then go straight into Complexity Analysis. If you already know Big-O well, skim its pattern-triggers table and jump to the amortized-analysis and recurrence sections; most people who "know Big-O" have not seen the potential method or the Master theorem's third case.
When the module is done, the next one is Module 1 · Linear Data Structures, which starts with Arrays & Strings.