对于以下每对函数 f(n) 和 g(n)，要么是 f(n) = O(g(n))，要么是 g(n) = O(f(n))，但不是两者。确定是哪种情况

For each of the following pairs of functions f(n) and g(n), either f(n) = O(g(n)) or g(n) = O(f(n)), but not both. Determine which is the case

有 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)

坚持证明

证明

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

除以n得到

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

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

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

这是真的。