2,827 views

1 Answer

Best answer
5 votes
5 votes

$T(n) = T\left(\frac{2n}{3} \right) + 1$

So, at level $n$ of the algorithm we are recursively calling the problem for $2n/3$ and the cost specific to a level is $1$. So, we just need to count the number of levels (recursive calls) and that will be the total cost. 

$T(n) = T\left(\frac{2n}{3} \right) + 1 \\=  T\left(\frac{4n}{9} \right) + 2 \\=\cdots\\=T (1) + k.$

(We need not reach $T(1)$, but the smallest value possible for a given $n$ where recursion ends. But using $T(1)$ is fine for asymptotic analysis). 

Here, $k$ is such that ${\frac{2}{3}}^k n \leq 1 \implies k \lg \frac{2}{3} + \lg n \leq 0 \\ \implies -k \lg \frac{2}{3} \geq \lg n \\ \implies k \lg \frac{3}{2} \geq \lg n \\ \implies k \geq \lg_{\frac{3}{2}} n.$

So, $T(n) = \Theta \left( \lg n \right)$ assuming $T(n) = c, \text{for } n \leq 1.$


Alternatively we can use Extended Master theorem (easier for this question though previous method is needed for some questions). 

Here, case is 2.a as $a = 1, b = \frac{3}{2}, k = 0, p = 0.$

So, $T(n) = \Theta(\log n)$. 

selected by

Related questions

0 votes
0 votes
1 answer
1
lucasbbs asked Feb 28, 2022
6,578 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
1 votes
1 votes
1 answer
2
1 votes
1 votes
2 answers
3
mdboi asked Oct 28, 2022
740 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
1 votes
1 votes
1 answer
4