7
$\begingroup$

I'm looking at Jeffrey Erickson's Notes on the master theorem (page 10).

Part (b) of the theorem states that if $T(n) = aT(\frac{n}{b})+f(n)$, $af(\frac{n}{b}) = kf(n)$ and $k>1$ then T(n) is $\Theta(n^{\log_b(a)})$. But I get a different result.

Using recursion trees we have $$T(n) = \sum_{i=0}^{\log_b(n)} a^i f\left(\frac{n}{b^i}\right) = \sum_{k=0}^{\log_b(n)} k^i f(n)\,.$$

If $k<1$ then this is $\sim f(n)$ as desired. If $k=1$ then this is $\sim \log_b(n)f(n)$ as desired. But if $k>1$ then this is an ascending geometric series, so the last term dominates. Then we have $$\sim k^{\log_b(n)}f(n) = n^{\log_b(k)}f(n)\,,$$ which is wrong; the right answer is $\Theta(n^{\log_b(a)})$. Where does my reasoning go off the rails, and what is the correct solution?

Any help is appreciated.

EDIT: I think my answer is actually right, and is equivalent to Erickson's simpler answer. Note that $k^nf(n) = k^{n-1}af(\frac{n}{b}) ... = ka^{n-1}f(\frac{n}{b^k-1}) = a^nf(\frac{n}{b^k}).$ Hence $k^{\log_b(n)}f(n) = a^{\log_b(n)}f(1) \sim n^{\log_b(a)}$.

$\endgroup$
3
$\begingroup$

You can further simplify $n^{\log_b(k)}f(n)$.

We have $\frac{a}{k}f(\frac{n}{b}) = f(n)$. If $c = \log_b(n)$, we can apply this identity $c$ times to get $\left(\frac{a}{k}\right)^c f(1)$.

So $n^{\log_b(k)}f(n) = n^{\log_b(k)}\left(\frac{a}{k}\right)^c f(1) = k^{\log_b(n)}\left(\frac{a}{k}\right)^{\log_b(n)} f(1) = a^{\log_b(n)}f(1) = \Theta(n^{\log_b(a)})$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.