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

Question

there is 2 functions: f(n) = n + log n and g(n) = n√n

if f(n) = O(g(n)):

n + log n <= C * n√n

else if g(n) = O(f(n)):

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

stuck to prove that

Answer 1

To prove

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

divide by n to get

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

As log(n)/n goes towards zero when n goes towards infinity, you get

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

which is true.