1.2k views

The running time of an algorithm is represented by the following recurrence relation:

$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$

Which one of the following represents the time complexity of the algorithm?

1. $\Theta(n)$

2. $\Theta(n \log n)$

3. $\Theta(n^2)$

4. $\Theta(n^2 \log n)$

edited | 1.2k views

$a=1, b=3, \log_b a=0$

So $n^{\log_b a} = n^0=1$

$f(n)=n$

So, $f(n)=Ω(1)$

To, check Master theorem case 3, we need $c>0$,

$f(n/3)\leq c f(n)$

$c=1$

So using case  three of master theorem

$T(n)= \Theta(f(n)) = \Theta(n)$

edited by
a and b are reversed? Also, we have to ensure regularity condition for case 3.
Here, what significance does T(n)= n for n<=3 have?

Case III of Master's Theorem.