CODEWITHSUNDEEP
timetime-complexity
Diana
Diana

Reputation: 1437

Time complexity of n factorial

I have the following problem but I have no idea how to prove it

n! is
    Select one or more:
 a. O(n^{3}) 
 b. O((n/2)^{n}) 
 c. O((n/3)^{n}) 
 d. O((n+1)!) 
 e. O(n^{n})
 f. O(2^{n})

I was thinking of using the property that f(x) ∈ O (g(x)) if and only if there is a value x0 and a constant c>0 such that for all x >= x0 f(x)<=c*g(x)

That would mean for the last one: 

n! <= c*2^{n}, for all n>=n0
n!/2^n <=c, for all n>=n0

Is it correct if I state here that the inequality is false as n!/2^n tends to infinity and c is just a constant?

Applying this logic I got that n! is b.,c.,d.,e. but I'm not sure this is correct.

Upvotes: 1

Views: 5821

Answers (1)

templatetypedef
templatetypedef

Reputation: 373012

You are correct that n! ≠ O(2n) for precisely the reason you've mentioned.

For (b) and (c), you'll need a more nuanced approach. Stirling's approximation says that

n! = Θ(√n (n / e)n)

This might be useful in evaluating the limit of n! over quantities (b) and (c). If you do, you'll see that only one of the two bounds holds, not both.

And yes, (d) and (e) are correct.

Hope this helps!

Upvotes: 1

Related Questions