Doubt with a problem of grown functions and recursion tree

Question

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$ ?

• Yuval Filmus: Your calculation seems to be right, only the value of the constant $c$ depends on the constant hidden inside $\Theta(n^{\log_2 3})$.
• Jonathan Prieto-Cubides: Yes? thanks, I suppose that I should proof the Theta notation, I read it about how can I do it

Answer 1

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 2ドルn$ 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}})$$

• Yuval Filmus: 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}$.
• ronalchn: ah, thanks, didn't think of trying to rearrange it
• JeffE: Alternatively, notice that $(3/2)^{\log_2 n} = n^{\log_2 (3/2)} = n^{\log_2 3 - 1}$.