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?
what is answer?
my answer is coming θ (n4 log n )
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!).
please solve my question also then
https://gateoverflow.in/125870/solve-the-recurrence-using-any-method-just-solve-it
64.3k questions
77.9k answers
243k comments
79.6k users