[algorithm] Is log(n!) = T(n·log(n))?

I am to show that log(n!) = T(n·log(n)).

A hint was given that I should show the upper bound with nⁿ and show the lower bound with (n/2)^(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nⁿ to n·log(n) (i.e. log both sides of an equation), but that's kind of working backwards.

What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn't seem like a likely approach..

See Stirling's Approximation:

ln(n!) = n*ln(n) - n + O(ln(n))

where the last 2 terms are less significant than the first one.

I realize this is a very old question with an accepted answer, but none of these answers actually use the approach suggested by the hint.

It is a pretty simple argument:

n! (= 1*2*3*...*n) is a product of n numbers each less than or equal to n. Therefore it is less than the product of n numbers all equal to n; i.e., n^n.

Half of the numbers -- i.e. n/2 of them -- in the n! product are greater than or equal to n/2. Therefore their product is greater than the product of n/2 numbers all equal to n/2; i.e. (n/2)^(n/2).

Take logs throughout to establish the result.

http://en.wikipedia.org/wiki/Stirling%27s_approximation Stirling approximation might help you. It is really helpful in dealing with problems on factorials related to huge numbers of the order of 10^10 and above.

Sorry, I don't know how to use LaTeX syntax on stackoverflow..

For lower bound,

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
       >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
       = n/2 lg n - 1/2

lg(n!) >= (1/2) (n lg n - 1)

Combining both bounds :

1/2 (n lg n - 1) <= lg(n!) <= n lg n

By choosing lower bound constant greater than (1/2) we can compensate for -1 inside the bracket.

Thus lg(n!) = Theta(n lg n)

Thanks, I found your answers convincing but in my case, I must use the T properties:

log(n!) = T(n·log n) =>  log(n!) = O(n log n) and log(n!) = O(n log n)

to verify the problem I found this web, where you have all the process explained: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

This might help:

eln(x) = x

and

(lm)n = lm*n

Helping you further, where Mick Sharpe left you:

It's deriveration is quite simple: see http://en.wikipedia.org/wiki/Logarithm -> Group Theory

log(n!) = log(n * (n-1) * (n-2) * ... * 2 * 1) = log(n) + log(n-1) + ... + log(2) + log(1)

Think of n as infinitly big. What is infinite minus one? or minus two? etc.

log(inf) + log(inf) + log(inf) + ... = inf * log(inf)

And then think of inf as n.