Introduction to Algorithms and Complexity

You need to sign in or sign up before continuing.

reading · we frame, you read MIT or the canonical taught · we author, no canonical fits ↺ spirals back to earlier lessons

Course locked

Complete Discrete Mathematics first.

This course unlocks once you've finished its prerequisite. Open prerequisite →

Prerequisites

Discrete Mathematics not yet

Complete prerequisites first to enroll.

reading · 25 min + ~230 min canonical

What an Algorithm Is — Correctness and Termination

You've written code that ran without errors and produced the wrong answer. Every working engineer has. The compiler can verify that your syntax is legal; it cannot verify that you…

primary Abdul Bari Algorithms (YouTube)

preview →

reading · 30 min + ~230 min canonical L1

Asymptotic Notation: Big O, Big Omega, Big Theta

Two engineers argue about which of two functions is faster. One has timed them on her laptop and the first wins by 30 milliseconds. The other has timed them on his server and the …

primary Abdul Bari Algorithms (YouTube)

after L1 locked

reading · 30 min + ~230 min canonical L1

Analysing Iterative and Recursive Algorithms

Asymptotic notation gives you the vocabulary. Now you need the technique: looking at a piece of code and getting the Θ bound out of it without timing anything. That technique is c…

primary Abdul Bari Algorithms (YouTube)

after L2 locked

reading · 45 min + ~230 min canonical L1

Recurrences and the Master Theorem

You wrote a recursive function in the last lesson. You worked out its recurrence: T(n) = T(n/2) + Θ(1) for binary search, T(n) = 2T(n/2) + Θ(n) for merge sort, T(n) = T(n-1) + T(n…

primary Abdul Bari Algorithms (YouTube)

after L3 locked

reading · 40 min + ~230 min canonical L1

Amortized Analysis and Space Complexity

You're appending to a Ruby array in a loop. array << item looks like a constant-time operation — and most of the time it is. But every once in a while, Ruby's array implementation…

primary Abdul Bari Algorithms (YouTube)

after L4 locked

exercise reading · 15 min L1

Exercises: Easy (Warm-up)

- [ ] Rank these functions by growth: n, n log n, n^2, 2^n, n!, log n, n^3 — Big O fluency - [ ] Analyze time complexity of Ruby's Array#include? vs Set#include? — O(n) vs O(1) - …

after L5 locked

exercise reading · 30 min L1

Exercises: Medium (Core)

- [ ] Prove that O(n log n) + O(n) = O(n log n) — Formal Big O proof - [ ] Analyze time complexity of binary search (iterative and recursive) — Recurrence: T(n) = T(n/2) + O(1) - …

after L6 locked

exercise reading · 45 min L1

Exercises: Hard (Stretch)

- [ ] Analyze average-case complexity of quicksort with random pivot — Recurrence with expected values - [ ] Prove the lower bound of comparison-based sorting: Omega(n log n) — De…

after L7 locked

exercise reading · 60 min L1

Mini-Project

- [ ] Write a Ruby benchmarking suite — implement Benchmark.measure wrapper that tests Array vs Hash vs Set lookups on 10K, 100K, 1M elements; plot results with ASCII chart

after L8 locked

L10

project reading · 300 min L1

Project: Complexity Analyzer

Write a Ruby tool that takes a block of code, runs it with inputs of size 10, 100, 1000, 10000, measures wall-clock time, and fits the growth curve to O(1), O(log n), O(n), O(n lo…

after L9 locked

L11

project reading · 240 min L1

Project: Algorithm Race

Implement linear search, binary search, hash lookup, and tree lookup in Ruby. Benchmark all four on datasets of 1K to 1M elements. Generate a markdown report with timing tables. D…

after L10 locked

L12

assessment reading · 63 min L1

Self-Assessment: Introduction to Algorithms and Complexity

- [ ] What is Big O notation? How does it differ from Big Omega and Big Theta? - [ ] Explain the difference between best case, worst case, and average case analysis. Which one do …

after L11 locked

12 lessons. Read in order; spiral back when you need to. By the end you'll have used the core ideas twice — once on the abstract, once on something you'll meet at work next week.