The Gateway to Computer Science Excellence
+19 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)$

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

@srestha @Bikram   anyone can you tell me what is the significance of T(n) = n  , n <= 3   ( for n<=3. it would be  O(n)?)

as i think for larger input n > 3 T(n) recursive call T(n/3) + cn is invoked hence leads to O(n) but somehow if recursive call evaluate O(sqrt(n)) or more precisely < O(n) then its upper bound O(n) would be selected.

isn't it ? 

There may exist many algorithms to solve a given problem. Moreover, the same algorithm may be implemented in a variety of ways. It is now time to analyze the relative merits and demerits of different algorithms and of different implementations.

We are shortly going to introduce a set of theoretical tools that make this analysis methodical. In order to solve a problem, it is not sufficient to design an algorithm and provide a correct (bug-free) implementation of the algorithm. One should also understand how good his/her program is. Here "goodness" is measured by relative performance of a program compared to other algorithms and implementations.

This is where the true "computer science" starts. Being able to program does not qualify one to be a computer scientist or engineer. A good programmer is definitely a need for every modern society and it requires time and patience to master the art of good programming. Computer science goes beyond that by providing formal treatment of programs and algorithms.

Consider that an airplane pilot is not required to know any aerospace engineering and an aerospace engineer need not know how to run an airplane. We need both pilots and aerospace engineers for our society. In short, when you write (and perhaps sell) your programs or when you buy others' programs, you should exercise your ability to compare the apparent goodness of available programs.

The task is not always easy. Here are some guidelines for you.


2 Answers

+21 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.

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


T(n) = T(n/3) + cn

T(3) = 3

Solving the recurrence relation by substitution.

But before that let n = 3$^{k}$ for easy calculation.

T(n) = T(n/3) + cn

= T(n/9) + cn/3 + cn

= T(n/27) + cn/9 + cn/3 + cn




= T($\frac{n}{3^{k-1}}$) + $\frac{cn}{3^{k-2}}$ + $\frac{cn}{3^{k-3}}$ + .... + $\frac{cn}{3^{k-k}}$

= T(3) + [$\frac{cn}{3^{k-2}}$ + $\frac{cn}{3^{k-3}}$ + .... + $\frac{cn}{3^{k-k}}$]

= 3 + cn [$\frac{1-\frac{1}{3^{k-1}}}{1-\frac{1}{3}}$]

= 3 + cn [$\frac{3^{k-1}-1}{\frac{2}{3}\times 3^{k-1}}$]

= 3 + (3c/2) n [$\frac{\frac{n}{3}-1}{\frac{n}{3}}$]

= 3 + (9c/2) [${\frac{n}{3}-1}$]

= $\Theta (n)$

+7 votes
Answer is A.

Case III of Master's Theorem.
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
50,737 questions
57,370 answers
105,274 users