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?
$\Theta(n)$
$\Theta(n \log n)$
$\Theta(n^2)$
$\Theta(n^2 \log n)$
$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)$
answer is A.
Gatecse