in Algorithms
2,818 views
1 vote
1 vote
$$T(n)=T(2n/3)+1$$

Find the order of algorithm?
in Algorithms
2.8k views

1 Answer

5 votes
5 votes
Best answer

$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
by