CODEWITHSUNDEEP
algorithmbig-o
Richie Thomas
Richie Thomas

Reputation: 3265

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

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?

Upvotes: 5

Views: 19837

Answers (4)

user1196549
user1196549

Reputation:

The explanation says it: "Recall that big-Oh notation provides only an upper bound on the growth rate of a function as N gets large."

In this particular context, the upper bound can be read as "does not grow faster than N³".

It is true that 11N + 15lgN + 100 does not grow faster than N³.

Upvotes: 4

NirmalGeo
NirmalGeo

Reputation: 771

As many have already quoted a function f(n) which has upper bound say O(n) complexity is also O(n^2) , O(n^3), O(n^4)... etc

Does that make sense or if it gets confused, think in absolute layman terms.

Suppose an process takes max upper bound of 10 secs to execute, come whatever be the input we can conclude this :-

  • Whatever be the input the execution will complete in less or equal to 10 seconds.

If that is true, even the following is true :-

  • Whatever be the input the execution will complete in less or equal to 100 seconds.
  • Whatever be the input the execution will complete in less or equal to 1000 seconds.

and so on.......

And thus you can correlate the answer. Hope that gave you a glimpse.

Upvotes: 3

Abhishek
Abhishek

Reputation: 7045

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 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.

Upvotes: 4

lukegary
lukegary

Reputation: 108

Think of O(N^2) also being O(n^3), O(n^4) and so on. O(N^2) is always bound under O(n^3), therefore O(n^2) is indeed O(n^3).

http://en.wikipedia.org/wiki/Big_O_notation#/media/File:Big-O-notation.png

Upvotes: 3

Related Questions