GATE CSE 2009 | Question: 35

Question

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?

• A. $\Theta(n)$

• B. $\Theta(n \log  n)$

• C. $\Theta(n^2)$

• D. $\Theta(n^2 \log  n)$

Comments

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.

//cse.iitkgp.ac.in/pds/notes/performance.html

Answer 1

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.

Comments

@Deepak Poonia Sir, my bad. Thanks for the rectification with this line:-

 the so-called regularity condition is also satisfied as for some c<1,af(n/b)≤cf(n) (take c=0.5)

We just need to satisfy it for “some c<1”. If it satisfies, then regularity cond. also satisfies. 

---

@Abhrajyoti00

Thanks :)

---

Answer is fixed now. It’ll be interesting to see some examples where regularity condition fails – I remmeber one in GATE PYQ.

Answer 2

Answer is A.

Case III of Master's Theorem.

Comments

It's not case III. Don't remember the case number.

---

😖

Answer 3

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

Using Master's Method,
 

n^log₃1 = n^0 = 1

Since, 1 < cn

Therefore, T(n) = Θ(n)

Correct Answer is Option A.

Answer 4

Given the recurrence

\[
T(n)=
\begin{cases}
n, & n\leq 3\\
T\left(\frac{n}{3}\right)+cn, & \text{otherwise}
\end{cases}
\]

Expanding the recurrence,

\[
T(n)=T\left(\frac{n}{3}\right)+cn
\]

\[
=T\left(\frac{n}{3^2}\right)+c\frac{n}{3}+cn
\]

\[
=T\left(\frac{n}{3^3}\right)+c\frac{n}{3^2}+c\frac{n}{3}+cn
\]

Continuing,

\[
T(n)=T\left(\frac{n}{3^k}\right)
+cn\left(1+\frac13+\frac1{3^2}+\cdots+\frac1{3^{k-1}}\right)
\]

The recurrence reaches the base case when

\[
\frac{n}{3^k}\leq 3
\]

which gives

\[
k=\Theta(\log n).
\]

The summation

\[
1+\frac13+\frac1{3^2}+\cdots
\]

is a decreasing geometric progression with

\[
a=1,\qquad r=\frac13.
\]

Its sum is bounded by

\[
\frac{1}{1-\frac13}=\frac32,
\]

which is a constant.

Therefore,

\[
T(n)=\Theta(n).
\]

Hence, the correct answer is

\[
\boxed{\text{A. }\Theta(n)}
\]

Answer 5

Answer is A.

Case III (log power less than 0 ) of Master's Theorem