07-bigo

Lecture Notes on
“Big-O” Notation
15-122: Principles of Imperative Computation

Jamie Morgenstern
Lecture 7
May 28, 2012
1 Introduction
Informally, we stated that linear search was, in fact, a linear-time function,
that binary search “was logarithmic” (in running time), and counted out
the number of operations which mergesort executed, in a somewhat sloppy
fashion, and decided our implementation executed kn log(n) + dn + e for
k, d, e ∈ N constant, independent of our input size, n. In this lecture, we
will make formal these notions, and try to give some examples and moti-
vation for a framework for analysis of algorithms and programs known as
asymptotic complexity.
2 Motivation
Certain operations, such as addition, subtraction, or multiplication of two
ints, or reading an element of an array, are said to be constant time opera-
tions, in that they take some fixed unit of time for your processor to calcu-
late the result. Others, such as executing a for-loop or allocating a array,
instead take a processor time proportional to the bound on the for-loop, or
the size of the array which must be allocated. Different machines are faster
at some operations than others. For this reason, asymptotic analysis does
away with exact calculation of how many additions versus how many mul-
tiplications, and the relative time each takes, and instead say each is one
operation which takes one unit of time. Once we’ve done this, and swept
L ECTURE N OTES M AY 28, 2012

“Big-O” Notation L7.2
under the rug exactly how many timesteps each of these different opera-
tions take, it seems somewhat foolish to care very much about the differ-
ence between 2 and 3 operations, or 100 or 200 operations. This is why
asymptotic analysis works modulo multiplicative constants: n operations
versus 3n operations versus 100n are all considered equivalent.
Moreover, when we were counting operations made by functions we’ve
written, we didn’t pay particularly close attention to the number of oper-
ations the base case made, or whether we executed the loop n or n − 1 or
n+1 times. If there is some small input, all reasonable programs should run
quickly on them, and the overhead of printing or calling the function often
overwhelms the run time of the few operations occuring for small inputs.
Given some runtime of your program on a large input, the asymptotic com-
plexity of your code should give you a rough estimate of how much longer
the function would take on an even larger input. For this reason, we only
consider sufficiently large inputs when talking about asymptotic complexity.
3 Formal Definition
Given f, g : N → R+ , we say that f ∈ O(g) if there exists some constants c >
0, n0 ≥ 0 such that for every n ≥ n0 , f (n) ≤ cg(n). That is, for sufficiently
large n, the rate of growth of f is bounded by g, up to a constant c. f, g might
represent arbitrary functions, or the running time or space complexity of a
program or algorithm.
4 Mergesort ∈ O(n log(n))

In class, we said that mergesort is O(n log(n)). How do we formally argue
this? We drew the tree of calls, and argued that the depth of the tree was
roughly bounded by log2 (n). Since all we care about is an upper bound, we
can say we’ll only consider inputs of size 2i for some i, and pick the smallest
i for which 2i ≥ n. Then, the depth of the call tree is exactly log2 (n), and
each path from the root is exactly that long.
We then counted the amount of work which happened at each level:
splitting the array in two took some constant t operations, and merging the
results of the two recursive call took dk + e operations for some constants
d, t, where k is the size of the input at that level. At each level i, the input
size was roughly n/2i for each call, and there were roughly 2i calls at the
ith level. Once we’ve assumed the input size is a power of two, then we can
say the input size and number of calls are exactly n/2i and 2i , respectively,

Plog(n)
so there is (d(n/2i )+t)∗2i = dn+t2i work done at each level, or i=0 dn+
t2i = dn log(n) + tn. Now, we must show that dn log(n) + tn ∈ O(n log(n)).
In order to show this, we must find some c, n0 , and show that for any n ≥
n0 ,
dn log(n) + tn ≤ cn log(n)
.
Let’s set c = d + t, n0 = 2. Notice then that what me must show for all
n ≥ 2 has reduced to
dn log(n) + tn ≤ (d + t)n log(n)

This is true iff
tn ≤ tn log(n)
But, for n ≥ 2, log(n) ≥ 1, so n log(n) ≥ n and tn log(n) ≥ tn, as desired.
5 Other Examples
This section presents two other examples of using big “O” notation, and
their proofs. First, we show a piece of code, which we will analyze for time
complexity
for (int i = 0; i < n; i++) {

for (int j = i; j < n; j++) {
binsearch(A, i, j);
}
}
Recall that we said binary search was O(log(n)); we will use this as a
lemma and claim the above piece of code runs in time O(n2 log(n)). Why
is this? First, for a particular i, j, the inner loop does O(log(j − i)) work.
Since j ≤ n, i ≥ 0, this is upper bounded by O(log(n)). Then, binary search
is called a total of
n X
X n X
n
1= (n − i)
i=0 j=i i=0
X
n
n(n + 1) n2 − n
= n2 − i = n2 − =
2 2
i=0

times. Thus, the total number of operations is bounded, for some n1 , c1

determined by the O of binary search, for all n ≥ n1 ,
n2 − n
Number of Operations of loop ≤ c1 log(n)(
2
Now it remains to show that there is some c ≥ c1 , n∗ ≥ n1 (both
∗
inequalities are necessary for the above claim to hold), such that for all
n ≥ n∗ ,
n2 − n
c1 log(n) ≤ c∗ n2 log(n)
2
Let’s pick c∗ = c1 , n∗ = n1 . Then, we must show, for all n ≥ n1 ,
n2 − n
c1 log(n) ≤ c1 n2 log(n)
2
Observe that, since n ≥ 0, we have
n2 − n n2
c1 log(n) ≤ c1 log(n)
2 2
and also that
n2
≤ c1 log(n)n2
c1 log(n)
2
But these two inequalities give us exactly what we want, namely that
n2 − n
c1 log(n) ≤ c1 n2 log(n)
2
.
6 Theorems you can use without proof

Theorem 1 Sum of functions If f ∈ O(g), f ′ ∈ O(g ′ ), then
f + f ′ ∈ O(g + g ′ )
As a corrolary, if g = g′ , then
f + f ′ ∈ O(g)

Theorem 2 Product of functions If f ∈ O(g), f ′ ∈ O(g ′ ), then
f · f ′ ∈ O(g · g ′ )
Theorem 3 Power of functions If f ∈ O(g), then for all α > 0,
f α ∈ O(g α )
Theorem 4 Composition of functions If f ∈ O(g) and f ′ ∈ O(g′ ), then
f ◦ f ′ ∈ O(g ◦ g ′ )
Theorem 5 Constants Constants, c, don’t grow at all. That is, for any increasing
function f of N,
c ∈ O(f (n))
Theorem 6 Polynomials versus logs For any α > 0, a polynomial of that de-
gree grows asymptotically faster than a logarithm. I.e.,
log(n) ∈ O(nα )
Theorem 7 Polynomials of lower degree Higher-degree polynomials grow more

quickly. I.e., for any α, ǫ > 0,
nα ∈ O(nα+ǫ )

07-bigo

Uploaded by

Copyright:

Available Formats

07-bigo

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

07-bigo

Uploaded by

Copyright:

Available Formats

Lecture Notes on

15-122: Principles of Imperative Computation

L ECTURE N OTES M AY 28, 2012

4 Mergesort ∈ O(n log(n))

L ECTURE N OTES M AY 28, 2012

dn log(n) + tn ≤ (d + t)n log(n)

for (int i = 0; i < n; i++) {

L ECTURE N OTES M AY 28, 2012

times. Thus, the total number of operations is bounded, for some n1 , c1

6 Theorems you can use without proof

L ECTURE N OTES M AY 28, 2012

Theorem 2 Product of functions If f ∈ O(g), f ′ ∈ O(g ′ ), then

Theorem 3 Power of functions If f ∈ O(g), then for all α > 0,

Theorem 4 Composition of functions If f ∈ O(g) and f ′ ∈ O(g′ ), then

Theorem 7 Polynomials of lower degree Higher-degree polynomials grow more

L ECTURE N OTES M AY 28, 2012

You might also like