algorithm - 对于以下每对函数 f(n) 和 g(n)，f(n) = O(g(n)) 或 g(n) = O(f(n))，但不能同时使用两者。确定是哪种情况

Question

有 2 个函数：f(n) = n + log n 和 g(n) = n√n

如果 f(n) = O(g(n))：

n + log n <= C * n√n

否则，如果 g(n) = O(f(n))：

n√n <= C(n + log n)

坚持证明

标签： algorithmbig-ologarithm

Answer 1

证明

n + log(n) <= C*n*sqrt(n)

除以n得到

1 + log(n)/n <= C*sqrt(n)

当趋向无穷大log(n)/n时趋向零，你得到n

1 <= C*sqrt(n) for n -> infinity

这是真的。