# Solving recurrence relation

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)$

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)$.