in Algorithms
21,083 views
3 votes
3 votes
how do i apply master theorem to this?

https://s17.postimg.org/x7xld2nf3/Screenshot_82.png

what is P and K here?
in Algorithms
21.1k views

1 comment

For Master's theorem, T(n)=aT(n/b) +Θ(n^k log^p n)  should satisfy the conditions: a>=1,  b>1, k>=0 and p= any real number.

The given relation: T(n)= 16T(n/4) +n!

has k=n so the condition is violated since k is not a constant. So, how can we apply Master's Theorem?

2
2

3 Answers

2 votes
2 votes
The recurrence is of the form T(n)=aT(n/b) +$\Theta ($ $n^{k}log^{p}n$ )

a=16,b=4

So,a<$b^{k}$=16<$4^{n}$  (If p<=0,T(n)=$\Theta (n^{k}log^{p}n)$)

n! can be written as $n^{n}$

So, T(n)=$\Theta (n^{n})$=$\Theta (n!)$

p=0 and k=n here

4 Comments

how can u apply master theorem when K is not constant??
2
2
$n^n \neq n!$ and even asymptotically this is not correct. We can just do $n! = O\left(n^n\right)$ - cannot replace $O$ with $\Theta$ here.
1
1

what is answer?

my answer is coming θ (n4 log n )

0
0
Answer is $\Theta (n!)$ and anything else is negative mark in GATE.
4
4
2 votes
2 votes

The recurrence is of the form T(n)=aT$\left ( \frac{n}{b} \right )$ + F(n) 

Here Since F(n) is (n!) which O(nn) i.e. n! = O(nn) [order of Oh means approximately not exact] 

  SO according to 3rd case of Master Theorem

 (nlogba ) is (n2) is less than F(n) which is  (n!) beacause  n! = O(nn).

So We can say T(n) = O(n!).

1 comment

0
0
1 vote
1 vote
Here the term n! is dominating in the given recurrence equation.  So, the overall time complexity will be n!. You need not apply substitution method here.