Please provide me a solution of Max-Heapify using Recursion Tree
-
06-11-2019 - |
Question
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.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange