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

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Learn more about Collectives

Teams

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Learn more about Teams It should be


    Thetha(n!)

if I am not wrong! Try using the theorem 4.1 stated in page 94 of CLRS – kiner_shah Dec 23, 2018 at 6:05 They look different, although I am not sure if they really are the same and just have different representations – kiner_shah Dec 23, 2018 at 6:11

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

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question . Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.
Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers .