Prove Ө(log 1 + log2 + log3 + log4 +... + logn) = Ө(n log n)

Question

Prove Ө(log2 *log3 *log4 *...*logn) = Ө(n log n)

That is, prove both the the big Oh and big Omega side.

Comments

We observe that log 1 + log2 + log3 + log4 +... + logn = log (1.2.3.4..n) = log (n!)

Answer 1

log1 + log 2 + log 3 + ...... + log n = log ( 1*2*3 .... *n) = log(n!)

log1 + log 2 + log 3 + ...... + log n  <= log n + log n + log n + ..... + log n

                                                      <= n log n

log1 + log 2 + log 3 + ...... + log n  = O(n log n)

log1 + log 2 + log 3 + ...... + log n  >= n/2 log n/2

log1 + log 2 + log 3 + ...... + log n  = big-omega(n log n)

so, log1 + log 2 + log 3 + ...... + log n  = Theta(n log n)

Answer 2

Hi there

Simplely, you are already be able to compare two function.

They are the same n items on both side, like A₁*A₂*...A_n  and B₁*B₂*...B_n and here we got A_n = log_nn and B₁ = B₂ = B_n = log₂n (hopes you means that is based 2  by convention)

It is clear that A₁ = log₂n = B₁ = log₂n ; A₂​=log₃n < B₂ = log₂n, A₃ = log₄n < B₃= log₂n ...

for most easy example, log₂4=2, log₄4 = 1, log₈4 < 1 the larger the base is, the smaller the log_an is.

so...each item in the array A is equal or less than the counterpart in array B, thus, A = O(B) //BigOh

Comments

Thank you Winterrollx. But what I actually want to know is whether log2n *log3n *... *lognn = Theta((log n)^n), not big-Oh. Otherwise that is a too simple question to ask. I have edited the question.