Solving recurrence relation

Question

I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$

                   npk
    /               |                 \
   /                |                  \ 
T(n,p,k/2)    T(n,p/4,k)     T(n/8,p,k)

the max height of the recursion tree is $ \log_{8}n $ and the cost of each level is at most npk so i guess the answer is $\Theta (npk \log_{8}n) $

Is my answer right?

Answer 1

The cost at each level isn't $npk$. Let's look at the first few levels.

1. The cost at the top level, $l=0$, is indeed $npk$.
2. At the next level ($l=1$) you have three recursive calls: $T(n,p,k/2)$, $T(n,p/4,k)$, and $T(n/8,p,k)$ with costs $npk/2, npk/4, npk/8$ for a total cost at level two of $$ \frac{npk}{2}+\frac{npk}{4}+\frac{npk}{8}=npk\cdot\frac{7}{8} $$
3. At the subsequent level you have nine recursive calls and if you do a bit of arithmetic you see that the total cost at that level ($l=2$) is $$ npk\cdot\left(\frac{7}{8}\right)^2 $$
4. You can show inductively that the cost at level $l$ will be $$ npk\cdot\left(\frac{7}{8}\right)^l $$ so the total cost up to and including level $M$ will be $$ T(n,p,k)=\sum_{l=0}^Mnpk\cdot\left(\frac{7}{8}\right)^l=npk\cdot\frac{1-(7/8)^{M+1}}{1-7/8}<8npk $$ since, as $M$ increases $(7/8)^{M+1}\rightarrow 0$. In other words, $T(n,p,k)=O(npk)$

It's clear that $T(n,p,k)>npk$, since that's the contribution at level zero, so we have, finally, $T(n,p,k)=\Theta(npk)$.