关于渐近运行时行为的问题
question regarding asymptotic runtime behavior
我们知道 log(n) = O(sqrt n )
我想知道说 log(n) 是 theta( sqrt n ) 是否有效。
在数值上，我证明了它是正确的；但我不太确定。
需要一些帮助
log n 不在 Theta(sqrt n) 中，因为 sqrt n 渐近地大于 log n，这意味着 log n 不在 [=15= 中].换句话说，sqrt n 不能是 log n.
的渐近下界
参考this big theta的定义。在定义中用 sqrt n 代替 g(n) 并用 log n 代替 f(n)，您会发现可以轻松找到 k2 和 n0，这样满足定义（这就是为什么 log n 在 O(sqrt n) 中），而找到合适的 k1 将被证明是不可能的（这就是为什么 log n 不在 Omega(sqrt n)).
我们知道 log(n) = O(sqrt n ) 我想知道说 log(n) 是 theta( sqrt n ) 是否有效。 在数值上，我证明了它是正确的；但我不太确定。 需要一些帮助
log n 不在 Theta(sqrt n) 中，因为 sqrt n 渐近地大于 log n，这意味着 log n 不在 [=15= 中].换句话说，sqrt n 不能是 log n.
参考this big theta的定义。在定义中用 sqrt n 代替 g(n) 并用 log n 代替 f(n)，您会发现可以轻松找到 k2 和 n0，这样满足定义（这就是为什么 log n 在 O(sqrt n) 中），而找到合适的 k1 将被证明是不可能的（这就是为什么 log n 不在 Omega(sqrt n)).