Algorithms · 4 lessons
Divide & ConquerSplit, solve, combine
Divide and conquer is where O(n log n) comes from: halve the problem, recurse, merge the results. Merge sort and quicksort are its famous examples; here it is treated as a general method, with the Master Theorem for working out the cost.
Why learn Divide & Conquer
Where it shows upWhy halving makes it faster
Comparing n things pairwise takes n², but splitting in half, solving each and merging takes n log n. The Master Theorem saves you from deriving the recurrence every time.
Cryptography and big numbers
RSA raises a number to a several-hundred-digit power modulo another. Fast exponentiation halves the exponent each step, finishing in a few hundred multiplications instead of never.
→ Lesson: Fast Exponentiation"How many pairs are out of order?"
Measuring how far apart two rankings are is really counting inversions. Count them during merge sort's merge step and it costs nothing extra.
→ Lesson: Count InversionsLessons
4 lessons#AlgorithmComplexityDifficultyStatus
01Master Theorem Solving recurrencesThe three cases of T(n) = aT(n/b) + f(n)Used for: Reading off the cost of a divide-and-conquer algorithm quickly—Space —available02Maximum Subarray Maximum subarrayThe divide-and-conquer version next to Kadane's linear oneUsed for: Best buy-and-sell window, signal analysisO(n log n) / O(n)Space O(log n)available03Fast Exponentiation Fast exponentiationHalve the exponent, recursively or with bit iterationUsed for: RSA, modular arithmetic, matrix powers for FibonacciO(log n)Space O(1)available04Count Inversions Counting inversionsCount them during merge sort's merge stepUsed for: Ranking similarity, measuring how unsorted data isO(n log n)Space O(n)available