are sets of functions.

Intuitively:

contains functions whose dominant term is at most that of .

contains functions whose dominant term is strictly smaller than that of .

contains functions whose dominant term is at least that of .

contains functions whose dominant term is equal to that of .

Definitions of "Big Oh"

is a set of functions.

is in if

This is read as "There exists a such that, for all but a finite number of s, is bounded above by .

In other words,

where is the threshold above which this is true. This is shown in the figure, where :

For example, consider

Since once gets large enough,

Let's be more rigorous: We must find a and such that

From the equation, guess that . Then

Since when , must be greater than and (from the last line above) must be greater than .

Therefore, if and ,

and that proves that .

Definition of "Little Oh"

is in "little-oh" of if

In other words, no matter how big is, is eventually bounded above by .

In other words, eventually is strictly smaller than , regardless of the coefficient in front of the dominant term of .

Definition of "Omega"

is in if

In other words, is eventually greater than .

is a lower bound of .

Note that if and only if .

Definition of "Theta"

is in if

In other words, and are eventually within a constant factor of each other.

but this isn't a "tight bound".

is a tight bound for if and only if

In other words, if there's no function, , that lies in the gap between and , then is a tight bound for .

For example, is not a tight bound for because the function lies in the gap between and . That is,

but

• Always use and for upper bounds.
• Always use for lower bounds.
• Never use for lower bounds.

A word on notation: In some texts, like CLR, you may see the notation

This is equivalent to our notation,

Always use our notation.