CHOOSE1

CHOOSE1

Which of the following is not bounded by O(n^2)?

•  (15^10) * n + 12099
•  n^1.98
•  n^3 / (sqrt(n))
•  (2^20) * n

Good solution:

The big O gives an upper bound. It doesn’t have to be tight - just means the function won’t exceed it for n > some constant. In this case O(n^2) serves as an upper bound for a, b and d. Functions a and d are linear - more to the order of O(n). Function b has a power just shy of 2 so it can still be bounded.

The case of function c is different. sqrt(n) = n^0.5
c = n^3 / n^0.5 = n^(3-0.5) = n^2.5 which is greater than n^2. Therefore n^2 can not serve as an upper bound here.
You could use it as a lower bound though - function c is omega(n^2).