runtime - 关于渐近运行时行为的问题

Question

我们知道 log(n) = O(sqrt n ) 我想知道说 log(n) 是 theta( sqrt n ) 是否有效。在数字上，我证明了它是正确的；但我不太确定。想要一些帮助

Answer 1

log nis NOT in Theta(sqrt n)，因为sqrt n渐近大于log n，这意味着log n不在Omega(sqrt n). 换句话说，sqrt n不能是 的渐近下界log n。

参考这个大θ的定义。在定义中替换sqrt nforg(n)和log nfor f(n)，您会发现很容易找到满足定义的 ak2和n0这样的定义（这就是为什么log n在 中O(sqrt n)），而找到合适的k1将证明是不可能的（这就是为什么log n不在 中Omega(sqrt n)）。