educative.io

Educative

Why time complexity is n! not n* n!?

we have n! different string results. but we need go through n character to build a string. which mean time complexity is n* n! not n!.

Hi Franklin,

Let’s start with the total number of recursive calls. For a string of length n, we make n recursive calls. These in return have n - 1 calls. The third level of calls will have n - 2 calls and so on.

This exponential growth of calls results in O(e.n!) where e is the exponential constant. Since we ignore constants, the complexity becomes O(n!).

Have a look at this video to understand it better:
(https://www.youtube.com/watch?v=nYFd7VHKyWQ)

Best Regards,
Educative Team.