1
$\begingroup$

$$T(n) = 2T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + 5$$

What is the time complexity of the given algorithm in $\theta$ notation.

Thanks in advance.

$\endgroup$
  • $\begingroup$ I tried to create a recursion tree but I could not find the answer. $\endgroup$ – g3d Feb 5 '14 at 20:40
  • $\begingroup$ Perhaps you could write out some of the recursion tree that you created, I think that may be the right path to follow. $\endgroup$ – abiessu Feb 5 '14 at 20:57
  • $\begingroup$ Please use \Theta. $\endgroup$ – Did Feb 5 '14 at 21:49
1
$\begingroup$

The shift $S(n)=T(n)+\frac52$ yields $$S(n)=\color{red}{\bf 2}\cdot S(n/\color{green}{\bf 2})+S(n/\color{green}{\bf 4}), $$ then a general result is that $$S(n)=\Theta(n^a), $$ where $a$ solves the equation $$1=\color{red}{\bf 2}\cdot\color{green}{\bf 2}^{-a}+\color{green}{\bf 4}^{-a},$$ that is, $$a=\log_2(\sqrt2+1)\approx1.2715533. $$ To prove this, proceed by induction, that is, assume that the property $$c\cdot n^a\leqslant S(n)\leqslant C\cdot n^a$$ holds for every $n\leqslant N-1$, for some suitable positive $c$ and $C$, and show that it holds for $n=N$ as well.

$\endgroup$
0
$\begingroup$

If $T(n)=2T\left(\frac n2\right)+T\left(\frac n4\right)+5$ then one expansion results in

$$T(n)=4T\left(\frac n4\right)+2T\left(\frac n8\right)+10+2T\left(\frac n8\right)+T\left(\frac n{16}\right)+5+5\\=4T\left(\frac n4\right)+4T\left(\frac n8\right)+T\left(\frac n{16}\right)+20$$

A second expansion brings

$$T(n)=8T\left(\frac n8\right)+4T\left(\frac n{16}\right)+20+8T\left(\frac n{16}\right)+4T\left(\frac n{32}\right)+20\\+2T\left(\frac n{32}\right)+T\left(\frac n{64}\right)+5+20\\ =8T\left(\frac n8\right)+12T\left(\frac n{16}\right)+6T\left(\frac n{32}\right)+T\left(\frac n{64}\right)+65$$

So we have an increasing number of terms per expansion, and apparent-quadratic behavior in the constant term $(5\cdot 1, 5\cdot 4, 5\cdot 13,\dots)$. One more expansion should help clarify these behaviors:

$$T(n)=16T\left(\frac n{16}\right)+8T\left(\frac n{32}\right)+40+24T\left(\frac n{32}\right)+12T\left(\frac n{64}\right)+60\\+12T\left(\frac n{64}\right)+6T\left(\frac n{128}\right)+30+2T\left(\frac n{128}\right)+T\left(\frac n{256}\right)+5+65\\= 16T\left(\frac n{16}\right)+32T\left(\frac n{32}\right)+24T\left(\frac n{64}\right)+8T\left(\frac n{128}\right)+T\left(\frac n{256}\right)+200$$

If we follow the constant term further, we now have $5\cdot 1, 5\cdot 4, 5\cdot 13, 5\cdot 40.$ The pattern of these constants is emerging, and appears to be $O(n^4)$. Continuing with the analysis in this direction should provide a satisfactory conclusion.

$\endgroup$
0
$\begingroup$

First of all note that this recurrence only depends on the number of bits of $n$ and not on their values, which simplifies things considerably.

Suppose we wish to solve $$T(n) = 2T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 5$$ where we set $T(0)=0.$

We unroll the recursion to obtain an exact formula for all $n:$ $$T(n) = 5 \times \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-2z-z^2}.$$

Now the roots of $1-2z-z^2 = 2-(z+1)^2$ are at $$-1 \pm \sqrt{2}$$ and their inverses are $$\rho_{1,2} = 1 \pm \sqrt{2}.$$ It follows that $$[z^j] \frac{1}{1-2z-z^2} = c_1 (1+\sqrt{2})^j + c_2 (1-\sqrt{2})^j.$$ Once we determine the coefficients we get $$[z^j] \frac{1}{1-2z-z^2} = \frac{2+\sqrt{2}}{4} (1+\sqrt{2})^j+\frac{2-\sqrt{2}}{4} (1-\sqrt{2})^j.$$ The conclusion is that the closed and exact formula for $T(n)$ is $$5\times \frac{2+\sqrt{2}}{\sqrt{2}\times 4} ((1+\sqrt{2})^{\lfloor \log_2 n \rfloor+1}-1)- 5\times \frac{2-\sqrt{2}}{\sqrt{2}\times 4} ((1-\sqrt{2})^{\lfloor \log_2 n \rfloor+1}-1).$$

If desired we may re-write this as $$-\frac{5}{2}+ 5\times \frac{2+\sqrt{2}}{\sqrt{2}\times 4} (1+\sqrt{2})^{\lfloor \log_2 n \rfloor+1}- 5\times \frac{2-\sqrt{2}}{\sqrt{2}\times 4} (1-\sqrt{2})^{\lfloor \log_2 n \rfloor+1}.$$

It follows that the complexity from the dominant asymptotic term is $$\Theta\left((1+\sqrt{2})^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\log_2(1+\sqrt{2})\times \log_2 n}\right) = \Theta\left(n^{\log_2(1+\sqrt{2})}\right).$$

The exponent here on $n$ is $$ 1.271553303,$$confirming the analysis by @Did.

A similar Master Theorem calculation can be found at this MSE link.

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