Which of the following is not O(n2)?

Key idea: Simplify each expression and compare its polynomial exponent to 2.

• n^3 / sqrt(n) simplifies to n^{3 - 1/2} = n^2.5. Because 2.5 > 2, this grows faster than n^2 and therefore is not O(n^2).

• (15^10) * n + 12099 has constant factors and constants that drop in asymptotic notation, so the dominant term is n. Thus it is O(n), which is also O(n^2).

• n^1.98 has exponent 1.98 < 2, so for large n it holds that n^1.98 ≤ n^2. Therefore n^1.98 = O(n^2).

• (2^20) * n is linear because 2^20 is a constant, so the function is O(n), and hence O(n^2) as well.

Answer: n^3 / sqrt(n) (because it simplifies to n^2.5, which grows faster than n^2).