Question

Select the correct inequality for the asymptotic order of growth of the function logn – √n?

1) logn – √n = O(logn)
2) logn – √n = O(√n)
3) logn – √n = O(n)
4) logn – √n = O(nlogn)

Answer 1

The correct asymptotic order of growth for the function log
`n - √n is O(√n),` as the √n term dominates the log n term for large values of n.

Step-by-step explanation:

To determine the asymptotic order of growth of the function log
`n - √n,` we should consider the behavior of each term separately as n approaches infinity. The natural logarithm function grows slower than the square root function. Therefore, as n gets very large, the
`√n` term will dominate, and the log n term will become relatively insignificant in comparison. Thus, the function log
`n - √n`will behave similarly to just
`-√n` for large values of n.

Comparing the options given, the correct inequality that describes the asymptotic order of growth for
`log n - √n` is:

`2) log n - √n = O(√n)`

This is because as n becomes very large, the negative square root term will dictate the growth behavior of the function, and thus, the function is bounded by a constant multiple of
`√n`, satisfying the definition of Big O notation.