Chapter 7
Asymptotic notation
Asymptotic notation is a tool for describing the behavior of functions on
large values, which is used extensively in the analysis of algorithms.
7.1 Definitions
O(f (n)) A function g(n) is in O(f (n)) (“big O of f (n)”) if there exist
constants c > 0 and N such that |g(n)| ≤ c|f (n)| for all n > N .
Ω(f (n)) A function g(n) is in Ω(f (n)) (“big Omega of f (n)”) if there exist
constants c > 0 and N such that |g(n)| ≥ c|f (n)| for all n > N .
Θ(f (n)) A function g(n) is in Θ(f (n)) (“big Theta of f (n)”) if there exist
constants c1 > 0, c2 > 0, and N such that c1 |f (n)| ≤ |g(n)| ≤ c2 |f (n)|
for all n > N . This is equivalent to saying that g(n) is in both O(f (n))
and Ω(f (n)).
o(f (n)) A function g(n) is in o(f (n)) (“little o of f (n)”) if for every c > 0
there exists an N such that |g(n)| ≤ c|f (n)| for all n > N . This is
equivalent to saying that limn→∞ g(n)/f (n) = 0.
ω(f (n)) A function g(n) is in ω(f (n) (“little omega of f (n)”) if for every
c > 0 there exists an N such that |g(n)| ≥ c|f (n)| for all n > N . This
is equivalent to saying that limn→∞ |g(n)|/|f (n)| diverges to infinity.
7.2 Motivating the definitions
Why would we use this notation?
105
, CHAPTER 7. ASYMPTOTIC NOTATION 106
• Constant factors vary from one machine to another. The c factor hides
this. If we can show that an algorithm runs in O(n2 ) time, we can be
confident that it will continue to run in O(n2 ) time no matter how fast
(or how slow) our computers get in the future.
• For the N threshold, there are several excuses:
– Any problem can theoretically be made to run in O(1) time for
any finite subset of the possible inputs (e.g. all inputs expressible
in 50 MB or less), by prefacing the main part of the algorithm with
a very large table lookup. So it’s meaningless to talk about the
relative performance of different algorithms for bounded inputs.
– If f (n) > 0 for all n, then we can get rid of N (or set it to zero) by
making c large enough. But some functions f (n) take on zero—or
undefined—values for interesting n (e.g., f (n) = n2 is zero when
n is zero, and f (n) = log n is undefined for n = 0 and zero for
n = 1). Allowing the minimum N lets us write O(n2 ) or O(log n)
for classes of functions that we would otherwise have to write
more awkwardly as something like O(n2 + 1) or O(log(n + 2)).
– Putting the n > N rule in has a natural connection with the
definition of a limit, where the limit as n goes to infinity of g(n)
is defined to be x if for each > 0 there is an N such that
|g(n) − x| < for all n > N . Among other things, this permits
the limit test that says g(n) = O(f (n)) if the limn→∞ fg(n)
(n) exists
and is finite.
7.3 Proving asymptotic bounds
Most of the time when we use asymptotic notation, we compute bounds using
stock theorems like O(f (n)) + O(g(n)) = O(max(f (n), g(n)) or O(cf (n)) =
O(f (n)). But sometimes we need to unravel the definitions to see whether
a given function fits in a given class, or to prove these utility theorems to
begin with. So let’s do some examples of how this works.
Theorem 7.3.1. The function n is in O(n3 ).
Proof. We must find c, N such that for all n > N , |n| ≤ c n3 . Since n3
is much bigger than n for most values of n, we’ll pick c to be something
convenient to work with, like 1. So now we need to choose N so that for all
n > N , |n| ≤ n3 . It is not the case that |n| ≤ n3 for all n (try plotting
Asymptotic notation
Asymptotic notation is a tool for describing the behavior of functions on
large values, which is used extensively in the analysis of algorithms.
7.1 Definitions
O(f (n)) A function g(n) is in O(f (n)) (“big O of f (n)”) if there exist
constants c > 0 and N such that |g(n)| ≤ c|f (n)| for all n > N .
Ω(f (n)) A function g(n) is in Ω(f (n)) (“big Omega of f (n)”) if there exist
constants c > 0 and N such that |g(n)| ≥ c|f (n)| for all n > N .
Θ(f (n)) A function g(n) is in Θ(f (n)) (“big Theta of f (n)”) if there exist
constants c1 > 0, c2 > 0, and N such that c1 |f (n)| ≤ |g(n)| ≤ c2 |f (n)|
for all n > N . This is equivalent to saying that g(n) is in both O(f (n))
and Ω(f (n)).
o(f (n)) A function g(n) is in o(f (n)) (“little o of f (n)”) if for every c > 0
there exists an N such that |g(n)| ≤ c|f (n)| for all n > N . This is
equivalent to saying that limn→∞ g(n)/f (n) = 0.
ω(f (n)) A function g(n) is in ω(f (n) (“little omega of f (n)”) if for every
c > 0 there exists an N such that |g(n)| ≥ c|f (n)| for all n > N . This
is equivalent to saying that limn→∞ |g(n)|/|f (n)| diverges to infinity.
7.2 Motivating the definitions
Why would we use this notation?
105
, CHAPTER 7. ASYMPTOTIC NOTATION 106
• Constant factors vary from one machine to another. The c factor hides
this. If we can show that an algorithm runs in O(n2 ) time, we can be
confident that it will continue to run in O(n2 ) time no matter how fast
(or how slow) our computers get in the future.
• For the N threshold, there are several excuses:
– Any problem can theoretically be made to run in O(1) time for
any finite subset of the possible inputs (e.g. all inputs expressible
in 50 MB or less), by prefacing the main part of the algorithm with
a very large table lookup. So it’s meaningless to talk about the
relative performance of different algorithms for bounded inputs.
– If f (n) > 0 for all n, then we can get rid of N (or set it to zero) by
making c large enough. But some functions f (n) take on zero—or
undefined—values for interesting n (e.g., f (n) = n2 is zero when
n is zero, and f (n) = log n is undefined for n = 0 and zero for
n = 1). Allowing the minimum N lets us write O(n2 ) or O(log n)
for classes of functions that we would otherwise have to write
more awkwardly as something like O(n2 + 1) or O(log(n + 2)).
– Putting the n > N rule in has a natural connection with the
definition of a limit, where the limit as n goes to infinity of g(n)
is defined to be x if for each > 0 there is an N such that
|g(n) − x| < for all n > N . Among other things, this permits
the limit test that says g(n) = O(f (n)) if the limn→∞ fg(n)
(n) exists
and is finite.
7.3 Proving asymptotic bounds
Most of the time when we use asymptotic notation, we compute bounds using
stock theorems like O(f (n)) + O(g(n)) = O(max(f (n), g(n)) or O(cf (n)) =
O(f (n)). But sometimes we need to unravel the definitions to see whether
a given function fits in a given class, or to prove these utility theorems to
begin with. So let’s do some examples of how this works.
Theorem 7.3.1. The function n is in O(n3 ).
Proof. We must find c, N such that for all n > N , |n| ≤ c n3 . Since n3
is much bigger than n for most values of n, we’ll pick c to be something
convenient to work with, like 1. So now we need to choose N so that for all
n > N , |n| ≤ n3 . It is not the case that |n| ≤ n3 for all n (try plotting
