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

That is, prove both the the big Oh and big Omega side.
in Asymptotic Analysis by AlgoMeister (752 points)
reshown by

3 Answers

0 votes
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)
by AlgoMeister (688 points)
–1 vote

I guess log2n *log3n *... *lognn=o((log n)n). // Small oh.

Proof:

log2n *log3n *... *lognn = (log n)n / (log 2 * log 3 ... * log n).

 lim(n->+Inf) [ (log n)n / ( log 2 * log 3 ... * log n ) ]  / (log n)n 

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

= 0.

Thus for an arbitrarily small positive constant c, you can always find an N s.t.

for all n>N, c(log n)n>log2n *log3n *... *lognn

This is definition of small oh.

by AlgoStar (380 points)
–1 vote

Hi there

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

They are the same n items on both side, like A1*A2*...An  and B1*B2*...Bn and here we got An = lognn and B1 = B2 = Bn = log2n (hopes you means that is based 2  by convention)

It is clear that A1 = log2n = B1 = log2n ; A2​=log3n < B2 = log2n, A3 = log4n < B3= log2n ...

for most easy example, log24=2, log44 = 1, log84 < 1 the larger the base is, the smaller the logan is.

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

by Active (284 points)
edited by
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.
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...