GATE CSE 1996 | Question: 2.12

Question

The recurrence relation

• $T(1) = 2$
• $T(n) = 3T (\frac{n}{4}) +n$

has the solution $T(n)$ equal to

• A. $O(n)$

• B. $O (\log n)$

• C. $O\left(n^\frac{3}{4}\right)$ 

• D. None of the above

Comments

n^(logb a) = n^(log4 3) = n^e where e<1

f(n) = n

hence, f(n) is polynomially greater then f(n).

Extended Master's theorm CASE3:

f(n)=Ω(n^(logb a)+e) e>0,then T(n)=Θ(f(n))

T(n)= Θ(n)

Answer 1

Answer: A

According to Master theorem,
$T(n) = aT(\frac{n}{b}) + f(n)$ can be expressed as:
$T(n) = [n^{\log_ba}][T(1) + u(n)]$
where $u(n) = \Theta(h(n))$ where $h(n) = \frac{f(n)}{n^{\log_ba}} = \frac{n}{n^{\log_43}} = n^{1-\log_43}$ as $h(n) = n^r$ where $r>0$.
So, $T(n) = [n^{\log_ba}][T(1) + u(n)] = T(n) = [n^{\log_43}][T(1) + \Theta(n^{1-\log_43})] = \Theta(n^{1})$.

Answer 2

Using Extended Master Theorem

$T(n)=3T(\frac{n}{4})+n^{1} \log^{0} n$

$a=3 , b =4 , k=1 , p=0$

case 3 : $a<b^{k}$  is true
case 3.a follows as $p=0$

Hence $T(n)$ is $\Theta (n^{1} \log^{0} ) \Rightarrow \Theta (n )$

Comments

Yes dude

---

@vupadhayayx86

Anything raised to the power 0 is 1.

 

---

@vishalshrm539 not 0 tho

Answer 3

Master theorem: $n^{\log_4 3} < n$, so it is $O(n)$.

Comments

@haider000  3T(n/4) is different  from T(3n/4)

---

thanks, @svas7246 for mentioning, I really did not pay the attention and miss read the question, will correct it.

---

You have calculated depth of the tree wrong. It should be like this –

depth of the tree getting reduced by n/4  at each level . And let’s say that at k ^th level size of our problem will hit 1 means T(1).

then n/4^k = 1

and k = log n (base4)

Answer 4

can directly use extended masters theorm

as here a < b^k

so t(n)=O(n^k log^p)    [:- k=1,p=0]

t(n)=O(n)