Notation:

We have f(n)=O[g(n)].

How to Read:

You should read equals like "is". Is means that everything over here is something over there.

Definition / Explanation:

This means that there are some suitable constants c and n0, such that f is bounded by cg(n) for all sufficiently large n. So, this is pretty intuitive notion. We have seen it before.

 f(n)=O[g(n)] means there are  constants c and n0,

Such that

0<=f(n)<=cg(n)

For all n>=n0

O() notation focuses on the largest term and ignores constants -

  • Largest term will dominate eventually for large enough n. -
  • Constants depend on “irrelevant” things like machine speed, architecture, etc.

Assumption:

We are going to assume that f(n) is non-negative here. And I just want f(n) to be bounded above by g(n).

Example:

We have seen a bunch of examples, but something like 2n^2=O(n^3) defined.

And roughly this means if you drop leading constants and low order terms then this is less than or equal to that.

Range:

So, big O corresponds roughly to less than or equal to.

Usage:

Used to find the upper bound of complexity or execution time.

big O is great for expressing upper bounds.

Represent:

Subset function.

Notation Nature:

Asymmetric

Big-O Taxonomy:

Growth Rate Name Notes