1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

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