Welcome to an introduction to the Big-O notation.
Asymptotic notation is used to express and compare
the growth rate of functions.
In our case, the functions will typically represent
the running times of algorithms.
We will define the asymptotic notations
in terms of nonnegative functions, since the running time
of an algorithm is always nonnegative.
We will focus on the notations most commonly used
in the analysis of algorithms, which are Big-O notation,
Big-Omega notation, and Big-Theta notation.
This lesson focuses on Big-O notation.
Asymptotic notation allows us to express the behavior
of a function as the inputs approach infinity.
In other words, it is concerned about what happens to f of n
as n gets larger, and is not concerned about the value
of f of n for small values of n.
We will define three of the most commonly used notations,
which, again, are Big-O notation,
Big-Omega notation, and Big-Theta notation.
In this lesson, we'll focus on Big-O notation.
If we let f be a nonnegative function,
we say f of n is Big-O of g of n,
written as f of n = Big-O of g of n,
if, and only if, there are positive constants
c and n sub0, such that f of n is less than or equal to
c X g of n for all n greater than or equal to n sub0.
So looking at the graph for a moment.
If our given function is f of n, the lower function,
notice that c X g of n is the upper function
for all n greater than or equal to n sub0,
where n sub0 is some value on the horizontal axis.
If f of n is a Big-O of g of n,
f of n grows no faster than g of n.
In other words, g of n is an asymptotic upper bound
or just upper bound of f of n.
And looking at the graph, hopefully that does make sense.
The equals in this statement, f of n = Big-O of g of n,
should be read and thought of as is, not equals.
You can think of it as a one way equals.
So saying f of n is Big-O of g of n is not the same thing
as saying Big-O of g of n is f of n, for instance,
with the latter statement not really making any sense.
An alternative notation is to write f of n
is an element of Big-O of g of n
instead of f of n is Big-O of g of n.
It turns out that Big-O of g of n
is actually the set of all functions
that grow no faster than g of n.
So the set notation is actually,
in some sense, more accurate.
The equals notation is used
because it comes in handy when doing algebra.
You can, essentially, think of these
as being two different notations for the same thing.
Similar statements are true
for the other asymptotic notations.
Let's take a look at a proof.
Let's prove that n squared + n is Big-O of n cubed.
Here, we have f of n = n squared + n,
and g of n is equal to n cubed.
Notice for n greater than or equal to 1,
n is less than or equal to n cubed,
and n squared is less than or equal to n cubed.
Notice when n is equal to one,
the left and right sides are equal,
and when n is greater than 1,
the left side is always less than the right side.
Therefore, it follows that n squared + n
is less than or equal to n cube + n cubed.
Notice to form this inequality,
we replaced n squared and n with n cubed.
And n cube + n cube is equal to 2n cubed,
therefore, we can state that n squared + n
is less than or equal to 2n cubed
for all n greater than or equal to 1.
Thus, we have shown that n squared + n is Big-O of n cubed
by definition of Big-O, with n sub0 equal to 1
and c = 2 where 2 is the coefficient of n cubed.
Before we go, let's take a look at this graphically.
In red, we have the graph of the given function f of n.
In blue, we have the graph of c X g of n = 2n cubed.
Notice f of n is less than or equal to
c X g of n for n greater than or equal to 1,
which does indicate f of n is Big-O of n cubed
for c = 2 and n sub0 equal to 1.
We can also say f of n grows no faster
than g of n = n cubed,
and g of n is an asymptotic upper bound of f of n.
I hope you found this helpful.