1.7k 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.7k 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
0
a and b are reversed? Also, we have to ensure regularity condition for case 3.
0
Here, what significance does T(n)= n for n<=3 have?
0
Just to make the question tricky I guess. The time complexity is always concerned for larger values of n which is in this case will contribute as T(n/3)+cn
0

@Pratik Gawali

T(n/3) can be applied on n which is atleast 3. We can't divide 2 numbers into 3 parts. For that atleast 3 numbers have to be there. But then shouldn't it be n<3 for 1st case instead of <= ?

Case III of Master's Theorem.

1
2