Big Oh notation (written with a ) states that:

is true if:
there exists constants and such that for all

It represents the upper bound for a function, and corresponds to the Worst Case running time.

Hint

Big-O can be thought of as a comparison. In other words the worst case running time will always be greater than or equal to the real running time.

Big-O Examples

Since is order , or :
Then it is, at most, roughly proportional to .

Or:

Since is order , or :
Then it is, at most, roughly proportional to

More Examples:

Lets consider a simple algorithm to fill an array with s.

Algorithm 1

// Code		     Cost
arr[0] = 0;       c1
arr[1] = 0;       c1
arr[2] = 0;       c1
...    
arr[N-1] = 0;     c1

Notice we have the same cost () for each line. We have lines, therefore:

Algorithm 2

This algorithm does the exact same thing using a for loop:

// Code                    Cost
for (i = 0; i < N; i++)     c2
	arr[i] = 0;             c1

Conclusion

Both algorithms consist of a constant () or () multiplied by plus a constant () or . Therefore, they are both .

Big-O: Set Definition

For the Set of functions {
there exists constants and
such that
for all }

We write to indicate that

Convention: A set in a formula represents an anonymous function in the set

Note

means "there exists"
means "for all"

Show that is :