Rung 1 — Complexity Audit Repository

Month: M1–M2 | Mode: Derivation | Platform: GitHub (public)

Most engineers memorize complexity. A small number can reproduce the derivation on demand. An even smaller number can explain why the recurrence relation produces the bound, where the constant factors come from, and what “space complexity including call stack” means for a recursive algorithm that never allocates a heap object. This rung is about becoming that smaller number.

The complexity-audit repository is not a cheat sheet. It is a structured derivation workbook committed to a public repo, where every claim is shown — not stated.

What It Is

A GitHub repository named complexity-audit containing a structured document (or a series of per-algorithm Markdown files) that derives the time and space complexity of 20+ algorithms from first principles.

“From first principles” means: you start from the pseudocode, you count operations, you set up the recurrence if recursive, and you solve the recurrence. You do not write “O(n log n) — see merge sort” and call it done. You write the recurrence, state what Master Theorem case applies (or use the substitution/iteration method), and produce the bound with the reasoning visible.

Required Coverage

Sorting (6)

  1. Bubble Sort — count comparison and swap operations across passes

  2. Insertion Sort — best case vs. worst case derivation; why the best case is O(n)

  3. Selection Sort — derive why it’s always O(n²) regardless of input

  4. Merge Sort — set up T(n) = 2T(n/2) + O(n), apply Master Theorem Case 2

  5. Quick Sort — average case via recurrence on random partition; worst case derivation

  6. Heap Sort — derive heapify cost, buildHeap cost, extraction cost separately

Search (2)

  1. Linear Search — trivial but derive it formally to establish template

  2. Binary Search — set up T(n) = T(n/2) + O(1), solve; also iterative version operation count

Data Structure Operations (9)

  1. Dynamic Array — amortized O(1) push: derive via aggregate analysis (potential method optional)

  2. Linked List — insert/delete at position: derive why O(n) in worst case

  3. Stack — all operations O(1): derive and explain why (array-backed)

  4. Queue — circular buffer: derive why front/rear pointer arithmetic gives O(1)

  5. Hash Map — average vs. worst case: derive expected chain length under uniform hashing

  6. Min-Heap — heapify-up and heapify-down: derive via tree height argument

  7. BST (unbalanced) — search/insert/delete: derive average case (O(log n)) and worst case (O(n))

  8. BST (AVL or Red-Black) — search: derive why O(log n) is guaranteed via height bound

  9. Trie — insert and search: derive in terms of key length L, not n

3 Algorithms of Your Choice (3)

18–20. Three algorithms from your Phase 1–2 study. Good candidates:

  • KMP string matching (derive the failure function construction cost)

  • Two-pointer technique on a sorted array (derive why O(n) instead of O(n²))

  • Sliding window maximum (derive why deque approach gives O(n))

Format Per Algorithm

Each algorithm entry must contain all five sections:

## [Algorithm Name]

### Pseudocode
[Clean pseudocode — not copied from Wikipedia, written by you in a consistent style]

### Time Complexity Derivation
Step 1: [Identify the primitive operations being counted]
Step 2: [Count operations in terms of input size n]
Step 3: [For recursive algorithms, write the recurrence T(n) = ...]
Step 4: [Solve the recurrence OR apply Master Theorem with the case stated]
Step 5: [State the final bound: O(...)]

Best case: O(...) — [brief reason]
Average case: O(...) — [brief reason]  
Worst case: O(...) — [brief reason]

### Space Complexity Derivation
[Count auxiliary space: variables, data structures, call stack]
[For recursive algorithms: maximum call stack depth × stack frame size]
Space: O(...)

### Key Insight
[One sentence: what structural property of the algorithm produces this complexity?]

### Common Mistake
[One complexity claim that people get wrong about this algorithm, and why]

Acceptance Criteria

Before marking this rung complete, verify all of the following:

  • 20+ algorithms covered (minimum: all listed algorithms)

  • Every derivation includes the step-by-step reasoning (no “it’s obvious that…”)

  • Recursive algorithms include the recurrence relation

  • Space complexity includes call stack analysis for all recursive algorithms

  • All bounds are correct (cross-check against CLRS or a trusted reference after deriving)

  • A peer (friend, colleague, online connection) reads one derivation and says the reasoning is clear and reproducible

  • No derivation was produced by an LLM — you wrote the reasoning yourself

The cross-check against a reference is allowed after deriving, not before. The derivation must be yours. The verification can use external sources.

Where to Publish

  1. Create a public GitHub repository named complexity-audit

  2. Write a README.md that explains what the repo is and why you made it (2–3 sentences)

  3. Structure options: one large COMPLEXITY.md, or separate files per category (sorting/, data-structures/, search/)

  4. Pin the repo to your GitHub profile

  5. Optional but recommended: tweet or post on LinkedIn with “I derived complexity for 20 algorithms from scratch — here’s the repo” — even one share forces you to stand behind the work

Signal It Sends

“This person actually understands complexity. They didn’t memorize it.”

This is a rare signal. The overwhelming majority of software engineers, including strong ones, can state that merge sort is O(n log n). A fraction can reproduce the recurrence. Almost no one has derived it from scratch and documented the steps. A reader who opens this repository and sees clean, step-by-step derivations for 20 algorithms immediately knows they are looking at someone who did the work.

It also signals intellectual honesty: you didn’t just write the answers. You showed the work. That is the rarest thing of all.

Practical Notes

  • Start with bubble sort even if it seems trivial. The act of formalizing a trivial case builds the template you’ll use for harder cases.

  • Merge sort’s derivation is the most instructive. Spend extra time on it. The Master Theorem application is the skill that transfers to all divide-and-conquer analysis.

  • Dynamic array amortized analysis is the conceptually hardest entry. If you can’t derive it cleanly, use aggregate analysis (total cost / total operations) before attempting potential method.

  • For hash map: you’ll need to state your assumption (uniform independent hashing). That’s fine. Stating your assumptions is good derivation hygiene.

  • Timebox each derivation: 20–30 minutes. If you’re stuck after 30 minutes, note where you’re stuck and move on. Come back after looking at the recurrence material again.

Timeline

Week

Target

Week 1–2 (M1)

Derive sorting algorithms (6) + search (2)

Week 3–4 (M1)

Derive data structure operations (9)

Week 5–6 (M2)

Derive 3 algorithms of choice

Week 7 (M2)

Review, correct errors, clean up formatting

Week 8 (M2)

Publish, pin to GitHub profile, mark Rung 1 complete