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 npkso i guess the answer is $\Theta (npk \log_{8}n) $Is my answer right?
Solving recurrence relation
time complexity;recurrence relation
The cost at each level isn't $npk$. Let's look at the first few levels.The cost at the top level, $l=0$, is indeed $npk$.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}$$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$$ 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)$.