Tag
divide-and-conquer
- Mar 5, 2025 The Master Theorem and the Recursion Tree Behind Its Three Cases Divide-and-conquer recurrences are solved by comparing the work at the root with the work at the leaves. Where the three cases come from, and which recurrences slip past them. algorithms
- Oct 5, 2022 Randomized Quicksort and the Expected Comparison Count How choosing the pivot uniformly at random makes the 2n ln n comparison bound hold for every input, and where the expectation stops describing a single run. algorithms