Logarithmic series. Lower bound [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

开发者_JS百科

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

I am having some trouble, finding the lower bound for this series :

S = lg(n-2) + 2lg(n-3) + 3lg(n-4) + ... + (n-2)lg2.

The upper bound as I have figured out (and I explain below) is O (N^2 . lgN) Could you help me in finding out the lower bound on this.

My proof for the upper bound goes as :

S = lg [ (n-2)* (n-3)^2 * (n-4)^3 *.. *2^(n-2) ] = O ( lg n^(1+2+3+..+(n-1) ) = O ( n^2*log(n) )

EDIT:

Just a random thought. Can I assume the series to be closely approximated by Integral (xLogx), which happens to be O (X^2. lgX) ?? But this too, would give only an upper bound and not a lower bound.

---

lg(n-2) + 2lg(n-3) + 3lg(n-4) + ... + (n-2)lg2 > lg(n-2) + 2 lg(n-3) + ... + (n/2)log(n/2) =
= lg [(n-2) * (n-3)^2 * ... * (n/2)^(n/2)] > lg[(n/2) * (n/2)^2 * ... * (n/2)^(n/2)] =
= lg [(n/2)^(1+2+...+n/2)] = lg [ (n/2) ^ [(n^2)/4] = [(n^2)/4] * lg(n/2) = omega(n^2 * lgn)