### 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 termwill dominate eventually for large enough n. -Constantsdepend 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 |