Algorithm

Question

How is Σ (1/k * log k) = O( n log n) for k=1 to n?

Comments

∑(1/k)*logk=(log1)/1 +(log2)/2 + (log3)/3 + .... + (logn)/n

        =((log1)(2*3*4*..*n)+(log2)(1*3*4*5...*n)+....+(logn)(1*2*3*...*n-1)) / (1*2*..*n)                                       

                  =((log1)(2*3*4*..*n)+(log2)(1*3*4*5...*n)+....+(logn)(1*2*3*...*n-1)) / n!

                  ≤ log (n*n*n*...*n) ≊ log(n^n) = O(nlogn)

 

---

Thanks

---

BharathiCH Nidhi Budhraja

I am getting O(log²n) . What is the answer given???