4
$\begingroup$

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, enter image description here Recursion Tree by the my problem 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$ ?

$\endgroup$
  • $\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 Filmus Sep 17 '12 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$ – jonaprieto Sep 17 '12 at 4:23
2
$\begingroup$

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

$\endgroup$
  • 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$ – Yuval Filmus Sep 17 '12 at 23:12
  • $\begingroup$ ah, thanks, didn't think of trying to rearrange it $\endgroup$ – ronalchn Sep 18 '12 at 0:28
  • $\begingroup$ Alternatively, notice that $(3/2)^{\log_2 n} = n^{\log_2 (3/2)} = n^{\log_2 3 - 1}$. $\endgroup$ – JeffE Sep 19 '12 at 16:04

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.