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
scroll top