0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Sachin Bahukhandi Sep 29 '19 at 4:19
  • $\begingroup$ Master theorum gives us lg n $\endgroup$ – Sachin Bahukhandi Sep 29 '19 at 4:20
  • 1
    $\begingroup$ @SachinBahukhandi $\log_{\frac{3}{2}}(n) = \Theta(\log(n))$. $\endgroup$ – OmG Sep 29 '19 at 15:05
  • $\begingroup$ 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))$ $\endgroup$ – Sachin Bahukhandi Oct 1 '19 at 15:48
  • 1
    $\begingroup$ @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)}$. $\endgroup$ – OmG Oct 1 '19 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.