lg(n)是lg(N)的Omega吗？

Question

我在试着计算下面的表达式。我无法理解的地方是第3行到第4行。

Sigma(i=1 to n-1) (lg(n-i))

但我们能像第4行那样写吗？我不确定lg(n-i)是否是lg(n)的欧米茄。如果可能的话，我也想要直观的解释。谢谢。

​

​

Answer 1

log(n-i)绝对不是Omega(log(n))。反例是当i = n - 1。或i = n - c表示任何常量c。

顺便说一下，我们可以为第四行E[x] > sum_{k=n/2}{n} log(n/2) = n/2 log(n/2) = Theta(nlog(n))编写。因此，E[x]在Omega(n log (n))中，关于E[x]的说法是正确的。