Discrete Mathematics is a branch of mathematics that deals with discrete structures, which are structures that have distinct, separate, and countable elements. It is used to study algorithms, logic, and mathematical reasoning. The subject covers a range of topics, including set theory, graph theory...
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller kuldipkorat. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
