master-theorem

Master Theorem: Why is T(n)=16T(n/4)+n! considered Θ(n!)

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/

enter image description here

The confusing part here is that my friend says that the answer is actually O(n!) and not Θ(n!)... So I am really confused.

Solution

  • Theorem from CLRS:

    Master theorem

    In your case, a = 16, b = 4, f(n) = n!

    Let's calculate nlogba. That will be n^2

    Now, n! is definitely greater than n^(2-e) 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 bigtheta(n!)