21,173 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?

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
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 votes
1 votes
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.

Related questions

0 votes
0 votes
1 answer
1
lucasbbs asked Feb 28, 2022
6,581 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
1 votes
1 votes
1 answer
2
ItzDc asked Jun 3, 2022
2,857 views
I can't figure out how to proceed and which case it's falling under after calculating h(n)
1 votes
1 votes
1 answer
3
1 votes
1 votes
2 answers
4
mdboi asked Oct 28, 2022
743 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n