Please help me prove SUM(logi) is Omega(nlogn) (转载)# Programming - 葵花宝典
m*w
1 楼
【 以下文字转载自 CS 讨论区 】
发信人: MadCow (Very Mad), 信区: CS
标 题: Please help me prove SUM(logi) is Omega(nlogn)
发信站: BBS 未名空间站 (Wed Mar 12 19:31:53 2008)
I can prove it's O(nlogn), like:
log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn
How can it be omega(nlogn)??
发信人: MadCow (Very Mad), 信区: CS
标 题: Please help me prove SUM(logi) is Omega(nlogn)
发信站: BBS 未名空间站 (Wed Mar 12 19:31:53 2008)
I can prove it's O(nlogn), like:
log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn
How can it be omega(nlogn)??