I am having some problem trying to understand why
T(n)=16T(n/4)+n!
is considered
Θ(n!)
I am using the following master theorem below from here:
https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/
The confusing part here is that my friend says that the answer is actually O(n!) and not Θ(n!)... So I am really confused.
Theorem from CLRS:
In your case, a = 16, b = 4, f(n) = n!
Let's calculate 
. That will be n^2
Now, n! is definitely greater than 
and n^2, so we will use third case of the theorem.
Let c = 0.5. This gives on substitution, 16 * (n / 4)! <= 0.5 * n!
Let's put a value in n and check:
If n = 100, 16 * (100 / 4)! <= 0.5 * 100! which gives 16 * 25! <= 0.5 * 100!. This inequality is correct since 100! will be way larger than 25!. Even multiplying with 16 won't make it greater than 0.5 * 100!.
This will be true for other larger values of n. So the complexity according to theorem should be 
