complexity
5 free lessons tagged complexity across Computer Science, Science, Programming. Each one is a short sequence of focused steps with narration and a five-question quiz at the end — take them in any order, no signup required.
Which Technique Applies, and How to Tell
A procedure for deciding between greedy, dynamic programming, and neither. Write the recurrence, count the states, attempt the greedy proof, and read the failure. Includes the instance where greedy is optimal and off by a third depending on one word in the problem statement.
Designing a Dynamic Program: State, Transition, Order
Writing a dynamic program is three decisions, not a recurrence to memorise. This lesson works through choosing the state, deriving the running time from it, fixing the evaluation order, recovering the answer rather than its value, and why an O(nW) knapsack is not polynomial.
Optimal Substructure: The Property Both Techniques Need
Dynamic programming and greedy algorithms both rest on a structural property the problem either has or does not have. This lesson establishes it precisely, shows a problem that lacks it, and separates the three properties that decide which technique applies.
Algorithms where quantum beats classical (and where it doesn't)
Shor, Grover, Hamiltonian simulation, HHL — the catalog of known quantum-algorithmic speedups, what 'speedup' precisely means in each case, and the structural reasons most problems do not gain exponential advantage.
Intro to Big-O Notation
A beginner-friendly tour of Big-O: what it measures, the common growth classes, and how to spot them in your own code.