Algorithm complexity and big O notation

Question

I am taking an online class on algorithms and I had the following quiz. I got it wrong and am trying to understand the reason for the answer.

Which of the following is O(n^3)?

a) 11n + 151 gn + 100
b) 1/3 n^2
c) 25000 n^3
d) All of the above.

The correct answer is (d) all of the above. The reason is that Big-O notation provides only the upper bound on the growth rate of function as n gets large.

I am not sure why the answer is not (c). For example, the upper bound on (b) is less than n^3.

There's no "the" upper bound. There are many upper bounds. The Big-O notation specifies **an** upper bound. A related notation provides *the least* upper bound, but it's not the Big-O notation. — n. m. could be an AI, Apr 30 '17 at 17:54

score 3 · Accepted Answer · edited May 23 '17 at 11:46

3

The reason is that formally, big-O notation is an asymptotic upper bound.

So 1/3*n^2 is O(n^2), but it is also O(n^3) and also O(2^n).

While in every-day conversion about complexity O(...) is used as a tight (both upper and lower bound), the theta-notation, or Θ(...) is the technically correct term for this.

For more info see What is the difference between Θ(n) and O(n)?

edited May 23 '17 at 11:46

Community

1
1

answered Apr 30 '17 at 17:52

Yossi Vainshtein

3,845
4
23
39

Algorithm complexity and big O notation

1 Answers1