Hey,
How do you go about proving that log(n!) is big Theta of n log n?
shakunni -3 Light Poster
Grn Xtrm 84 Posting Pro in Training
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 700 Posting Maven
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.