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$
2
  • $\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$ Sep 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$ Sep 17, 2012 at 4:23

1 Answer 1

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$
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$
    – ronalchn
    Sep 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$
    – JeffE
    Sep 19, 2012 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.