edited by
12,209 views
31 votes
31 votes

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 by

2 Answers

Best answer
28 votes
28 votes

Comparing with the recurrence form of Master Theorem $T(n) = aT(n/b) + f(n)$

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

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

$f(n)=cn$

So, $f(n)=\Omega(n^{\log_b a+\epsilon})$ holds for any $\epsilon < 1$ and this is the third case of Master theorem. But Master theorem also requires (only case 3) that regularity condition be satisfied (this ensures that $f(n)$ is still dominant when the recurrence go deeper) which is $af(n/b) \leq df(n)$ for some $d < 1$ and all sufficiently large $n.$ (Using $d$ here as $c$ is already used in $f(n))$

Here we get, $f(n/3) \leq df(n)$

$\implies cn/3 \leq dcn \implies 1/3 \leq d$

Thus we can use any $1/3 \leq d < 1$ to satisfy the regularity condition and Master theorem case 3 is satisfied. Now, applying case $3$ we get 

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

answer is A.

edited by
Answer:

Related questions

48 votes
48 votes
5 answers
3
Kathleen asked Sep 22, 2014
21,147 views
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time com...