I'm confused to conclude the recursion tree method a guess for the next recurrence:
$$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$
I write some costs for the levels of tree, you can see, but I'm confusing in the final guess. I know for the master theorem that the answer for the guess is like that
$$\Theta(n^{\log_2 3}) $$ but in the steps by tree and I don't belive, you can see my error (?). How can I finished or know the outcome for this method to calculate $T(n)$?
thanks,
And the final conclusion is (?)
$$=2 n^{\log_2 3}+\Theta(n^{\log_2 3})\leq cn^{\log_2 3} \rightarrow \ \ T(n)\in\Theta(n^{\log_2 3})$$ with $c=3$ ?
-
$\begingroup$ Your calculation seems to be right, only the value of the constant $c$ depends on the constant hidden inside $\Theta(n^{\log_2 3})$. $\endgroup$– Yuval FilmusSep 17, 2012 at 3:55
-
$\begingroup$ Yes? thanks, I suppose that I should proof the Theta notation, I read it about how can I do it $\endgroup$– Jonathan Prieto-CubidesSep 17, 2012 at 4:23
1 Answer
Instead of having logarithms in the working, I'll substitute $n=2^m$: $$ T(n) = n\sum_{i=0}^{m} \left(\frac{3}{2}\right)^i = n \frac{\left(\frac{3}{2}\right)^{m+1}-1}{\frac{3}{2}-1} = 2n \left(\left(\frac{3}{2}\right)^{m+1}-1\right) = 2n \left(\frac{3}{2}\right)^{m+1}-2n $$ I believe the previous step is where you didn't expand the $2n$ into the first term. I am also not making any guess of what the master theorem or order of complexity is. Guesses should not be necessary anyways, since we just assume $T(1) \in \Theta(1)$.
Simplifying by keeping only the first term, and removing constants:
$$T(n) \in \Theta(n 1.5^{\log{n}})$$
Then, with some rearranging:
$$n 1.5^{\log_2{n}} = 2^{\log_2{n}}1.5^{\log_2{n}} = 3^{\log_2{n}}=2^{\log_2{3}\log_2{n}}=n^{\log_2{3}}$$
Thus:
$$T(n) \in \Theta(n^{\log_2{3}})$$
-
1$\begingroup$ Notice that $n (3/2)^{\log_2 n} = 2^{\log_2 n} (3/2)^{\log_2 n} = 3^{\log_2 n} = 2^{\log_2 3 \log_2 n} = n^{\log_2 3}$. $\endgroup$ Sep 17, 2012 at 23:12
-
$\begingroup$ ah, thanks, didn't think of trying to rearrange it $\endgroup$– ronalchnSep 18, 2012 at 0:28
-
$\begingroup$ Alternatively, notice that $(3/2)^{\log_2 n} = n^{\log_2 (3/2)} = n^{\log_2 3 - 1}$. $\endgroup$– JeffESep 19, 2012 at 16:04