edited by
7,119 views

4 Answers

Best answer
23 votes
23 votes

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

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

Related questions

26 votes
26 votes
1 answer
4
Kathleen asked Oct 9, 2014
5,109 views
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...