3,215 views

1 Answer

Best answer
5 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
Position:
Show:

Related questions

0 0 votes
1 answers 1 answer
11.0k
11.0k views
lucasbbs asked Feb 28, 2022
10,988 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...
5 5 votes
4 4 answers
1.2k
1.2k views
NullPointer_Pro asked Dec 24, 2025
1,176 views
Consider the following recurrence relation describing the running time of an algorithm: $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$$$(Base\ condition: T(1) =...
0 0 votes
1 1 answer
317
317 views
arbpass asked Sep 11, 2025
317 views
How to check if f(n) is polynomially greater than g(n)?
1 1 vote
1 1 answer
1.8k
1.8k views
mdboi asked Oct 29, 2022
1,797 views
how do i apply master theorem to this?