∑ Log(i) = big theta(f(n))？

Question

给定 S(n) = ∑ Log(i) 使得 sigma 从 i=1 运行到 n 什么是简单函数 f(n) 使得和 S(n) 在 f(n) 的大 Theta 中？

我正在考虑 f(n) = loglogn，因为我相信它在求和的初始值 log1=0 和求和的终值 logn 的边界内。

因此满足big theta的定义..

这样对吗？否则请帮忙

Answer 1

画一幅画，让自己相信以下内容。

log(x)从1到N的积分< ∑ Log(i) < log(x)从1到N+1的积分。

因此 N log(N) - N < ∑ Log(i) < (N+1) log(N+1) - (N+1).

两个边界都是 N log(N) 的大 Theta。