# Please provide me a solution of Max-Heapify using Recursion Tree

I tried my best to solve the recurrence relation.

$$T(n) \le T(2n/3) + \Theta(1)$$

Using the recursion tree.

I could reach out the boundary condition when at depth i:

$$i= \log_{3/2}n$$

Can someone please help me out in adding the costs and taking out the upper-bound. I know at each depth the cost is increasing by a power of $$2$$, i:e- $$2^i$$.

What I have done so far is adding up the costs:

$$\sum_{i=0}^{log_{3/2}n-1} 2^i+ \theta(log_{3/2}n)$$.

Please correct me if I am wrong. Thank you.

$$T(n) = T(2n/3) + \Theta(1) = T(2^2n/3^3) + \Theta(1) + \Theta(1)$$
Now you can see $$T(n) = \Theta(\log_{\frac{3}{2}}(n))$$. Because each time $$\Theta(1)$$ is added up to reach to the leaf of the expnasion tree. Also, you can reach this result using the master theorem.
• Master theorum gives us lg n – Sachin Bahukhandi Sep 29 '19 at 4:20
• @SachinBahukhandi $\log_{\frac{3}{2}}(n) = \Theta(\log(n))$. – OmG Sep 29 '19 at 15:05
• But how come $\Theta(\log_{\frac{3}{2}}(n))$= $\Theta(\log_2(n))$. Also it's $\Theta(\log_2(n))$ and not $\Theta(\log_{10}(n))$ – Sachin Bahukhandi Oct 1 '19 at 15:48
• @SachinBahukhandi the constants greater than 1 are the same! 10 or 2. no different in the final result. Using this property in $\log$ to prove: $\log_a(b) = \frac{\log_c(b)}{\log_c(a)}$. – OmG Oct 1 '19 at 21:43