# 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.

Try to solve the recurrent by expanding equality case:

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

• But the T(2^i/3^i) yields up to n^\log_{3/2}n.so won't this be considered. How can I prove this equal to big-oh(lg n) Sep 29, 2019 at 4:19
• Master theorum gives us lg n Sep 29, 2019 at 4:20
• @SachinBahukhandi $\log_{\frac{3}{2}}(n) = \Theta(\log(n))$.
– OmG
Sep 29, 2019 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))$ Oct 1, 2019 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, 2019 at 21:43