The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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 (59.4k points)
edited by | 1.4k views

2 Answers

+18 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 (31.4k 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?
+7 votes
Answer is A.

Case III of Master's Theorem.
answered by Boss (19.7k 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

35,507 questions
42,829 answers
42,183 users