Big O/ Big Theta notation

[shakunni]

Hey,
How do you go about proving that log(n!) is big Theta of n log n?

[Grn Xtrm]

This doesnt really have anything to do with Java or software development for that matter. Make sure your posting in the right forum next time you start a thread. This question is probably best suited for the computer science forum.

[BestJewSinceJC]

I'll give you some hints and leave the rest of the work (such as using the definition of theta to come up with the values that prove it's big theta) up to you. But these are just my thoughts, no guarantee that it's correct so listen at your own risk.

Consider that n! = n (n-1)(n-2). . . 1. Now consider that n!, therefore, is < n^n, which can be shown simply by aligning each term in n! and each term in n^n.

Now use the logarithmic property: loga(x^r) = r loga(x)

Then use your theta values after finding them to wrap it up. In fact (if it is true and theta values can be found) you don't even need any other logic, unless it was requested by your instructor.