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? Algorithms algorithms master-theorem + – vishwa ratna asked Feb 19, 2017 vishwa ratna 21.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply Bongbirdie commented Mar 4, 2017 reply Follow Share 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 votes 2 votes Please log in or register to add a comment.
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 Arnabi answered Feb 19, 2017 Arnabi comment Share Follow See all 4 Comments See all 4 4 Comments reply indrajeet commented Mar 24, 2017 reply Follow Share how can u apply master theorem when K is not constant?? 2 votes 2 votes Arjun commented Apr 17, 2017 reply Follow Share $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 votes 1 votes LavTheRawkstar commented Apr 18, 2017 reply Follow Share what is answer? my answer is coming θ (n4 log n ) 0 votes 0 votes Arjun commented Apr 18, 2017 reply Follow Share Answer is $\Theta (n!)$ and anything else is negative mark in GATE. 4 votes 4 votes Please log in or register to add a comment.
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!). Prashant. answered Apr 18, 2017 Prashant. comment Share Follow See 1 comment See all 1 1 comment reply LavTheRawkstar commented Apr 18, 2017 reply Follow Share please solve my question also then https://gateoverflow.in/125870/solve-the-recurrence-using-any-method-just-solve-it 0 votes 0 votes Please log in or register to add a comment.
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. Rajesh Panwar answered Dec 29, 2018 Rajesh Panwar comment Share Follow See all 0 reply Please log in or register to add a comment.