HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Doubt with a problem of grown functions and recursion tree

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemrecursionwithdoubtandfunctionsgrowntree

Problem

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

Solution

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

Context

StackExchange Computer Science Q#4583, answer score: 2

Revisions (0)

No revisions yet.