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.