Factorials

For all natural numbers x∈N the factorial function, x!, is defined as

	    
x! = 1         if x=0,
x! = x(x-1)!   otherwise.
	    
	  

When reasoning asymptotically (big O, little omega, big Theta) we have the following:

• x!=O(xx)
• x!=ω(2x)
• lg(x!)=Θ(x lg x)

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.