patternMinor
Trouble understanding the master theorem, from Jeffrey Erickson's Notes
Viewed 0 times
fromunderstandingericksonthejeffreynotesmastertheoremtrouble
Problem
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 $k1$ 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)}$.
(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 $k1$ 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)}$.
Solution
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)})$
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)})$
Context
StackExchange Computer Science Q#77422, answer score: 3
Revisions (0)
No revisions yet.