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

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 abc. 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 enter image description here

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.

Leave a Comment