The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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 }

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)$

asked in Algorithms by Veteran (52.1k points)
edited by | 2.2k views
Can anyone tell me which method is best to solve the Recurrence relation?
1 Substitution Method
2 Recursion Tree
3 Master's Theorem.

2 Answers

+19 votes
Best answer

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

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


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

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

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


So using case  three of master theorem

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

answer is A.

answered by Boss (30.9k points)
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?
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

@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 <= ?

+7 votes
Answer is A.

Case III of Master's Theorem.
answered by Boss (19.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,811 questions
54,540 answers
75,603 users