How are the following functions O(N^3)?

Question

I'm taking the "Intro To Algorithms" course on Coursera, and I've arrived at the video which deals with Big-Theta, Big-Omega and Big-O notation. The end-of-video quiz presents the following question:

Q: Which of the following functions is O(N^3)?

a) 11N + 15lgN + 100
b) (N^2)/3
c) 25,000*(N^3)
d) All of the above

I answered "c" and was told my answer was incorrect, and that the correct answer is actually "d". The explanation provided by the course wasn't much help:

Recall that big-Oh notation provides only an upper bound on the growth
rate of a function as N gets large. In this course, we primarily use 
tilde notation because it more accurately describes the function—it 
provides both an upper and lower bound on the function as well as the 
coefficient of the leading term.

I was under the impression that one should drop the lesser-order terms (i.e. "15lgN + 100") and focus only on the highest-order terms. Furthermore, I can't see how N^3 could be the upper bound on a quadratic (as opposed to a cubic) function like N^2.

So my question is, why are "a" and "b" classified as O(N^3) in this case?

Answer 1

Do you know, f(n) = O(g(n)) implies f(n) <= constant* g(n), right? In other words, it means, when you plot the graph of f(n) and g(n) then after some value of, g(n) will always be more than f(n).

Here g(n) is N^3 and remaining comes in f(n). Now, N^3 is always >= options a, b, c. hence answer id D :)

Edit: Following statements are true,

• n=O(n)
• n=O(n^2)
• n=O(n^3)

But only n = O(n) is tight upper bound and that is what we should use in time complexity derivation of algorithms. If we are using 2nd and 3rd option, then we are misusing the Big-O notation or let's say they are upper bounds but not tightly bounded!

Edit 2: See following image

G(x) is tight upper bound for F(x) and H(x) is upper of F(x) but not tight! Still we would say, F(x)=O(G(x)) & F(x)=O(H(x)). When somebody in exam/interview ask for time complexity they are asking for tight bounds, but not an upper bound. Unfortunately, tight upper bound and upper bound terms are used in exams/interviews interchangeably.