in Algorithms edited by
5,684 views
22 votes
22 votes

The recurrence relation

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

has the solution $T(n)$ equal to

  1. $O(n)$

  2. $O (\log n)$

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

  4. None of the above

in Algorithms edited by
5.7k views

4 Answers

23 votes
23 votes
Best answer

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

edited by
29 votes
29 votes

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

by

4 Comments

Yes dude
1
1

@vupadhayayx86

Anything raised to the power 0 is 1.

 

1
1
@vishalshrm539 not 0 tho
1
1
17 votes
17 votes
Master theorem: $n^{\log_4 3} < n$, so it is $O(n)$.
edited by

4 Comments

@haider000  3T(n/4) is different  from T(3n/4)
0
0
thanks, @svas7246 for mentioning, I really did not pay the attention and miss read the question, will correct it.
0
0

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)

0
0
0 votes
0 votes
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)
Answer:

Related questions