Prove that log(n) ∈ Θ( nlog(n) )

[s3a]

Homework Statement

The question and solution are in the attachment.

Homework Equations

Big O, Ω, Θ definitions. Also, I think logarithmic identities.

The Attempt at a Solution

It's the part shown in red that I am stuck at. I tried to expand log(n!) to log(n) + log(n-1) + ... + log(1) but I can't see how to get log(n) + log(n-1) + log(n-2) + ... + log(n/2 + 1) + log(n/2) + ... + log(2) + log(1) = n/2 * log(n/2) + n/2 * log(1) out of that.

Any help getting past this step would be greatly appreciated!
Thanks in advance!

 

[rcgldr]

I can't see how to get log(n) + log(n-1) + log(n-2) + ... + log(n/2 + 1) + log(n/2) + ... + log(2) + log(1) = n/2 * log(n/2) + n/2 * log(1) out of that.

The book isn't stating those are equal instead it's stating it's greater than or equal:

log(n) + log(n-1) + log(n-2) + ... + log(n/2 + 1) + log(n/2) + ... + log(2) + log(1) >= n/2 * log(n/2) + n/2 * log(1)

 

[s3a]

Thanks for clarifying that it's an inequality but I'm still confused as to the reasoning with all the n/2 terms as well as why those curly braces are being chosen in their entirety (because that seems to imply that it's exactly equal to the thing under each respective curly brace).

If I am being unclear, please tell me.

 

[rcgldr]

all the n/2 terms

It's because a list of n terms from 1 to n was separated into two lists, {1 to n/2} {n/2+1 to n}.

seems to imply that it's exactly equal to the thing under each respective curly brace.

Not equal but greater than or equal. For example {log(1) + log(2) + ... + log(n/2)} is greater than {log(1) + log(1) + ... + log(1)}.

 

[s3a]

Okay, I now see that the goal was to choose the smallest (or even a smaller) term from each curly brace such that it's less than or equal to the initial log(n!).

I am now stuck at the step:
n/2 [log(n) - 1] >= n/2 [log(n) - 1/2 * log(n)]

How do I justify that step?

 

[rcgldr]

It's ok up to this point:

n/2 log(n/2) + n/2 log(1), since log(1) == 0, this becomes
n/2 log(n/2) + 0 == n/2 log(n/2)

n/2 log(n/2) ==
n/2 (log(n) - log(2))

Then there's an issue:

n/2 (log(n) - log(2)) ?= n/2 (log(n) - 1)

This means log(2) == 1, which is only true if this is log base 2 (log₂(...)

So ignoring this substitution and continuing

n/2 (log(n) - log(2))

note that 1/2 log(4) == log(2), { since sqrt(4) == 2, so 1/2 log(4) == sqrt(log(4)) == log(2) }

if n >= 4, then 1/2 log(n) >= log(2) and

n/2 (log(n) - log(2)) >= n/2(log(n) - 1/2 log(n))

since log(n) - 1/2 log(n) = 1/2 log(n),
n/2(log(n) - 1/2 log(n)) = n/2(1/2 log(n)) = 1/4 n log n

 

[Max.Planck]

Basically the question is prove: lim n->infty log(n!)/ (nlog(n)) = c, for some constant c.
If you expand n! you get n*(n-1)*(n-2)...etc, which will be n^n-O(n^(n-1)). For large n, n^n will be the dominant term.

 

[s3a]

Thanks for the answers.

rcgldr, the whole 1/2 log(4) == log(2) thing was just an attempt to match my teacher's solution, right?

For example, if I replaced log(2) with log 1/4 * log(16) instead of replacing it with 1/2 * log(4) and then replaced log(16) with log(n) as follows:
n/2 * [log(n) - 1/4 * log(n)]
= 4n/8 log(n) - n/8 log(n)
= 3/8 * n * log(n)

it would be a correct yet slightly different approach to what the teacher did, right?

 

[rcgldr]

3/8 * n * log(n) ...
it would be a correct yet slightly different approach to what the teacher did, right?

Yes, but in this case only if n >= 16.

 

[s3a]

I have another mini-question: Is the ending of the solution provided a typo?

More specifically, should n log(n) <= 4 n log(n) be n log(n) <= 4 log(n!) instead?

 

[rcgldr]

Should n log(n) <= 4 n log(n) be n log(n) <= 4 log(n!) instead?

That's what I think it should be.