In fact both are true. log(n!) is actually Θ(nlogn). See math.stackexchange.com/questions/46892/…
Since this limit tends toward infinity, we see that n log n is not Θ(n).
If you choose N=10 , nlogn is always greater than n .
Yes for Binary search the time complexity in Log(n) not nlog(n). So it will be less than O(n). But N*Log(N) is greater than O(N).
Remember that
log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)
You can get the upper bound by
log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
= n*log(n)
And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:
log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)
= log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
>= log(n/2) + ... + log(n/2)
= n/2 * log(n/2)
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.
Sorry, I don't know how to use LaTeX syntax on stackoverflow..
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.
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With