3
$\begingroup$

This problem is given in "Introduction to Algorithms", by Thomas H. Cormen.

I have the answer to it, but I don't understand it.

The answer is, $T(n) = \Theta(n)$.

It would be really good if you can explain it using recursion tree.

$\endgroup$
3
$\begingroup$

You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.

Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n.$$

Then we have the following exact formula for $T(n)$: $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Now let $\rho_{1,2,3}$ be the inverses of the roots of $$1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3$$ where $$\rho_1 \approx 0.9196433771 \quad \text{and} \quad \rho_{2,3} \approx -0.2098216888 \pm 0.3031453647 i$$ so that $\rho_1$ dominates.

Solving for $c_{1,2,3}$ in $$[z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} = c_1 \rho_1^j + c_2 \rho_2^j + c_3 \rho_3^j$$ we obtain $$c_1 \approx 0.6184199255 \quad \text{and} \quad c_{2,3} \approx 0.1907900392 \mp 0.01870058304 i.$$

To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving $$ T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} 2^{\lfloor \log_2 n \rfloor} \\ = 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} (c_1 \rho_1^j + c_2 \rho_2^j + c_3 \rho_3^j) = 2^{\lfloor \log_2 n \rfloor} \left( c_1 \frac{1-\rho_1^{\lfloor \log_2 n \rfloor +1}}{1-\rho_1} + c_2 \frac{1-\rho_2^{\lfloor \log_2 n \rfloor +1}}{1-\rho_2} + c_3 \frac{1-\rho_3^{\lfloor \log_2 n \rfloor +1}}{1-\rho_3} \right).$$ This bound is actually attained.

For an upper bound, consider the case of a string of ones, $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k \\ = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (c_1 \rho_1^j + c_2 \rho_2^j + c_3 \rho_3^j) (2^{\lfloor \log_2 n \rfloor +1} - 2^j) \\ = 2^{\lfloor \log_2 n \rfloor +1} \left( c_1 \frac{1-\rho_1^{\lfloor \log_2 n \rfloor +1}}{1-\rho_1} + c_2 \frac{1-\rho_2^{\lfloor \log_2 n \rfloor +1}}{1-\rho_2} + c_3 \frac{1-\rho_3^{\lfloor \log_2 n \rfloor +1}}{1-\rho_3} \right) \\ - \left( c_1 \frac{(2\rho_1)^{\lfloor \log_2 n \rfloor +1}-1}{2\rho_1-1} + c_2 \frac{1-(2\rho_2)^{\lfloor \log_2 n \rfloor +1}}{1-2\rho_2} + c_3 \frac{1-(2\rho_3)^{\lfloor \log_2 n \rfloor +1}}{1-2\rho_3} \right).$$ This bound too is actually attained.

To conclude we compute the asymptotics. We see that $|\rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to $$ 2^{\lfloor \log_2 n \rfloor} \left(\frac{c_1}{1-\rho_1} +\frac{c_2}{1-\rho_2} +\frac{c_3}{1-\rho_3} \right) = 8 \times 2^{\lfloor \log_2 n \rfloor}.$$

We also have $|2| > |2\rho_1|$ and hence the upper bound is asymptotic to $$ 2\times 2^{\lfloor \log_2 n \rfloor} \left(\frac{c_1}{1-\rho_1} +\frac{c_2}{1-\rho_2} +\frac{c_3}{1-\rho_3} \right) = 16 \times 2^{\lfloor \log_2 n \rfloor}.$$ It follows that $$ T(n) \in \Theta \left(2^{\lfloor \log_2 n \rfloor} \right) = \Theta\left(n\right)$$ with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $\lfloor \log_2 n \rfloor$ is off by almost one from the correct value $\log_2 n,$ which turns the sixteen back into eight.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Here are the top two layers of the recursion tree:

enter image description here

All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,\text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be $$ n+\left(\frac{7}{8}\right)n+\left(\frac{7}{8}\right)^2n+\left(\frac{7}{8}\right)^3n+\cdots $$ so we have a geometric series and thus $$ T(n)\le \frac{1}{1-\frac{7}{8}} = 8n $$ for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)\ge 2n$. Putting these together gives us the desired bound, $T(n)=\Theta(n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c \in \mathbb{Z}_{\gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{\log_2{n}}$, which is superlinear. $\endgroup$ – void-pointer Mar 22 '16 at 6:03
  • $\begingroup$ what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ? $\endgroup$ – vikkyhacks Jan 9 '17 at 14:15
2
$\begingroup$

Using Akra–Bazzi method

$$a_1=a_2=a_3=1$$

$$b_1=2, b_2=4,b_3=8$$

$$f(n)=n$$

$$a_i > 0, b_i > 0$$

$$\cfrac{a_1}{b_1^p}+\cfrac{a_2}{b_2^p}+\cfrac{a_3}{b_3^p}=1$$

$$\left(\cfrac{1}{2}\right)^p+\left(\cfrac{1}{4}\right)^p+\left(\cfrac{1}{8}\right)^p=1$$

$$T(n)=Θ\left(n^p\left(1+\int_n^1 \frac{f(x)}{x^{p+1}} \, dx \right)\right)$$

$$\int_n^1 \frac{x}{x^{p+1}} \, dx=n^{1-p}$$

$$\implies T(n)=Θ\left(n^p\left(1+ n^{1-p}\right)\right) = \left(n^p\right)*\left(n^{1-p}\right) = Θ\left(n\right)$$ Hence,

$$ T(n) = Θ\left(n\right) $$

                              a_1=a_2=a_3=1
                            b1=2 , b2=4 , b3=8
                                 f(n)=n

                               ai>0 , bi>0

                       (a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1 
                          (1/2)^p+(1/4)^p+(1/8)^p=1

                        T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))

                             ∫n1x/x^p+1dx=n^1-p

                      T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)

                                 T(n)=Θ(n)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ here is a mathjax guide to type maths on this site. $\endgroup$ – Siong Thye Goh Jan 27 '19 at 12:31
  • $\begingroup$ For anyone studying Algorithms from Intro to Algorithms by CLRS you can find this Akra-Bazzi method to solve such recurrences at the end of Divide and Conquer Chapter $\endgroup$ – Syed Souban Aug 14 '19 at 16:49

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.