snippetMinor
Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n)
Viewed 0 times
dividewithexamplerecurrencealgorithmandconquer
Problem
I'm working on some lecture notes and wondered if there was a good example algorithm for the recurrence equation
$$T(n) = T(n/2) + n$$
I know that I can do selection in this running time, but that is a probabilistic algorithm, and I was hoping not to introduce this algorithm at this point in my lecture notes. I plan to introduce the selection problem in a later chapter after describing quick-sort. Is there a good example of an algorithm that has this recurrence equation as worst-case?
$$T(n) = T(n/2) + n$$
I know that I can do selection in this running time, but that is a probabilistic algorithm, and I was hoping not to introduce this algorithm at this point in my lecture notes. I plan to introduce the selection problem in a later chapter after describing quick-sort. Is there a good example of an algorithm that has this recurrence equation as worst-case?
Solution
Bottom-up heap construction. Choose one application of sift-down as your unit of measurement. Then the recurrence is $T(n) = T(n/2) + n$.
If you want to go beyond that, you can say that choosing sift-down as a unit for measurement isn't quite accurate, and its runtime depends on the height $h$ of heap being sifted down in. But you can show that bottom-up heap construction is still $O(n)$ due to
$$0\cdot n + 1\cdot \frac{n}{2} + 2\cdot \frac{n}{4} + \cdots + h\cdot 1 = \sum_{h=0}^{\lg n} h\frac{n}{2^h} < n\sum_{h=0}^\infty \frac{h}{2^h}$$
and showing (or simply stating without proof in case you feel the students are not ready yet) that $\sum_{h=0}^\infty \frac{h}{2^h}$ converges to a constant.
If you want to go beyond that, you can say that choosing sift-down as a unit for measurement isn't quite accurate, and its runtime depends on the height $h$ of heap being sifted down in. But you can show that bottom-up heap construction is still $O(n)$ due to
$$0\cdot n + 1\cdot \frac{n}{2} + 2\cdot \frac{n}{4} + \cdots + h\cdot 1 = \sum_{h=0}^{\lg n} h\frac{n}{2^h} < n\sum_{h=0}^\infty \frac{h}{2^h}$$
and showing (or simply stating without proof in case you feel the students are not ready yet) that $\sum_{h=0}^\infty \frac{h}{2^h}$ converges to a constant.
Context
StackExchange Computer Science Q#93356, answer score: 2
Revisions (0)
No revisions yet.