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$

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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