Phase 0 Exit Criteria & Projects

Weeks 5–6 | Aug 29 – Sep 7, 2026

This phase has a concrete exit gate. You do not move to Phase 1 until you can meet every criterion below without external help. This isn’t gatekeeping — it’s the difference between building Phase 1 on solid ground vs. building it on sand. Two weeks of projects will also tell you, honestly, whether you’ve actually internalized this material or just read it.

Exit Criteria

You are done with Phase 0 when you can do ALL of the following without looking anything up:

Complexity Analysis:

  • Given any algorithm with single loops, nested loops, or loops that halve — derive its time complexity in under 2 minutes, showing the work

  • Given a recursive function, write the recurrence relation T(n) = … in under 1 minute

  • Apply the Master Theorem to classify any eligible recurrence in under 2 minutes

  • State the difference between O, Ω, and Θ accurately in one sentence each

  • Explain why dynamic array push_back is O(1) amortized, not O(n), without notes

Space Complexity:

  • Identify the space complexity of iterative vs. recursive algorithms, counting call stack depth

  • State when a recursive algorithm uses O(n) space even if no data structures are allocated

Mathematical Toolkit:

  • Prove that 1 + 2 + … + n = n(n+1)/2 by induction, from scratch, in 5 minutes

  • Write the loop invariant for binary search without looking at this document

  • Apply modular arithmetic properties to a multi-step computation

  • Recall the 5 logarithm identities in this document without reference

Problem-Solving Protocol:

  • Execute the 4-step protocol (Understand/Brute Force/Optimize/Code) on a new problem without being prompted

  • Write a loop invariant for any loop you write as a matter of habit

Project 1: Complexity Audit Sheet

What it is: A structured document where you derive the time and space complexity of 10 common algorithms you already know (or can look up), from scratch, with derivations.

The 10 algorithms:

  1. Bubble sort

  2. Selection sort

  3. Insertion sort

  4. Linear search

  5. Binary search

  6. Merge sort

  7. Fibonacci (recursive naive: fib(n) = fib(n-1) + fib(n-2))

  8. Fibonacci (iterative)

  9. Power function (x^n, recursive: pow(x,n) = x * pow(x, n-1))

  10. Power function (fast exponentiation: x^n = x^(n/2) * x^(n/2))

For each algorithm, write:

  • The recurrence relation T(n) = … (for recursive) or the loop structure analysis (for iterative)

  • Time complexity with derivation

  • Space complexity with derivation (don’t forget the call stack)

  • What common mistake someone would make analyzing this

Acceptance criteria: All 20 complexity values correct (10 × time + 10 × space), derivations shown, no external lookup during the final write. You may look things up while learning, but the final document is from memory.

Time estimate: 3–5 hours across Weeks 5–6.

Project 2: Recurrence Solver

What it is: Solve 5 recurrences by at least two methods each (Master Theorem + substitution, or Master Theorem + recursion tree).

The 5 recurrences:

  1. T(n) = 2T(n/2) + O(n)

  2. T(n) = 4T(n/2) + O(n²)

  3. T(n) = T(n-1) + O(n) (Master Theorem doesn’t apply — use substitution)

  4. T(n) = 3T(n/3) + O(1)

  5. T(n) = 2T(n/4) + O(√n)

For each:

  • Apply Master Theorem if applicable (if not, explain why not)

  • Apply substitution method OR draw the recursion tree

  • State the final Θ bound

Acceptance criteria: 5/5 correct. Show all work. If you can’t do #3 without Master Theorem, that means you understand when Master Theorem doesn’t apply — that’s a pass.

Answers (don’t peek until you’ve tried):

  1. Θ(n log n)

  2. Θ(n² log n)

  3. Θ(n²) — write recurrence tree: T(n) = n + (n-1) + … + 1 = n(n+1)/2

  4. Θ(n^log₃3) = Θ(n) — wait, log₃3 = 1, f(n) = O(1) = O(n^(1-ε)), Case 1 → Θ(n)

  5. Θ(√n · log n) — c* = log₄2 = 0.5, f(n) = √n = n^0.5 = Θ(n^c*), Case 2 → Θ(n^0.5 · log n)

Time estimate: 2–3 hours.

Project 3: Rubber Duck Explanation

What it is: Record yourself (audio or video, even just for yourself) explaining Big-O to a rubber duck (or a wall, or a stuffed animal) for 5 uninterrupted minutes, without notes.

What to cover:

  • What Big-O measures and what it doesn’t

  • The difference between O(1), O(log n), O(n), O(n log n), O(n²)

  • One concrete example of why O(n log n) is dramatically better than O(n²) for n = 10⁶

  • Why amortized O(1) is still “constant time” for push_back even though some calls are O(n)

Acceptance criteria: You can explain the O(log n) complexity classes (O(log n), O(n log n)) without hesitation or filler. You don’t stumble on the definition or examples. You can explain the amortized argument in plain English.

Why this works: The Feynman technique — if you can explain it clearly, you know it. If you can’t explain it without hedging, you have a gap. Find the gap now, in Week 5, not in a job interview or Codeforces round.

Time estimate: 1 hour (including preparation).

Week-by-Week Schedule for Phase 0

Week 1 (Aug 1–7): Big-O Foundation

  • Study: 01_big_o_mastery.md — read all sections, work all 5 practice problems on paper

  • Practice: Analyze 5 algorithms you already know by hand (don’t look up answers first)

  • Habit: For every loop you write this week, state its complexity before running it

  • Time: ~10 hours

Week 2 (Aug 8–14): Recurrences

  • Study: 02_recurrence_relations.md — work all 4 problems on paper before reading solutions

  • Practice: Find 3 recursive algorithms (anywhere: textbooks, LeetCode solutions) and write their recurrences. Solve by Master Theorem.

  • Time: ~10 hours

Week 3 (Aug 15–21): Mathematical Toolkit

  • Study: 03_mathematical_thinking.md — work through induction proof on paper

  • Practice: Find and solve LeetCode Easy problems that are pure math (search “math” tag, pick 5)

  • Time: ~10 hours

Week 4 (Aug 22–28): Protocol + Invariants

  • Study: 04_pseudocode_and_invariants.md — trace all 3 algorithm examples on paper

  • Practice: Solve 3 LeetCode Easy problems using the full 4-step protocol. Write pseudocode before code. Write the invariant for every loop.

  • Time: ~12 hours

Week 5 (Aug 29 – Sep 4): Projects 1 & 2

  • Work: Complete Complexity Audit Sheet and Recurrence Solver

  • Review: Re-read anything you struggled with in Weeks 1–4

  • Time: ~12 hours

Week 6 (Sep 5–7): Project 3 + Exit Gate

  • Work: Record the rubber duck explanation

  • Gate: Run yourself through the exit criteria checklist above, honestly

  • If passing: Mark Phase 0 complete, begin Phase 1 on Sep 8

  • If not passing: Identify specific gaps, spend 2–3 more days closing them before advancing

  • Time: ~6 hours

A Note on Advancing

The 6-week timeline is a recommendation, not a hard rule. If you’re moving faster, great — advance early. If Week 6 arrives and you can’t pass the exit gate, don’t advance. Phase 1 built on an incomplete Phase 0 will cost you more time than the delay.

The exit gate is honest. If you can’t explain amortized analysis or apply the Master Theorem without notes, you will struggle to reason about heap operations and hash map analysis in Phase 1. The debt compounds.

Return to README.md · Next Phase: 02_core_data_structures/README.md