Algorithms R OBERT S EDGEWICK | K EVIN W AYNE

1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms F O U R T H E D I T I O N
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

 1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

Running time

“ As soon as an Analytic Engine exists, it will necessarily guide the future

course of the science. Whenever any result is sought by its aid, the question
will arise—By what course of calculation can these results be arrived at by
the machine in the shortest time? ” — Charles Babbage (1864)

how many times do you

have to turn the crank?

Analytic Engine
3
Cast of characters

Programmer needs to develo

a working solution.

Student might pla

Client wants to solve any or all of thes

problem ef ciently. roles someday.

Theoretician wants
to understand.

4
fi
e

Reasons to analyze algorithms

Predict performance

this course (COS 226)

Compare algorithms

Provide guarantees

Understand theoretical basis theory of algorithms (COS 423)

Primary practical reason: avoid performance bugs.

client gets poor performance because programmer

did not understand performance characteristics

5
.

Some algorithmic successes

Discrete Fourier transform

Break down waveform of N samples into periodic components
Applications: DVD, JPEG, MRI, astrophysics, …
Brute force: N 2 steps Friedrich Gaus
1805
FFT algorithm: N log N steps, enables new technology.

time
quadratic
64T

32T

16T
linearithmic
8T
linear

size 1K 2K 4K 8K

6
s

Some algorithmic successes

N-body simulation
Simulate gravitational interactions among N bodies
Brute force: N 2 steps
Barnes-Hut algorithm: N log N steps, enables new research. Andrew Appel
PU '81

time
quadratic
64T

32T

16T
linearithmic
8T
linear

size 1K 2K 4K 8K

7
.

The challenge

Q. Will my program be able to solve a large practical input

Why is my program so slow ? Why does it run out of memory ?

Insight. [Knuth 1970s] Use scienti c method to understand performance.

8
fi
?

Scienti c method applied to analysis of algorithms

A framework for predicting performance and comparing algorithms

Scienti c method
Observe some feature of the natural world
Hypothesize a model that is consistent with the observations
Predict events using the hypothesis
Verify the predictions by making further observations
Validate by repeating until the hypothesis and observations agree

Principles
Experiments must be reproducible
Hypotheses must be falsi able

Feature of the natural world. Computer itself.

9
fi
fi
.

fi
.

 1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

 Example: 3-SUM

3-SUM. Given N distinct integers, how many triples sum to exactly zero

% more [Link] a[i] a[j] a[k] sum

30 -40 10 0
30 -40 -20 -10 40 0 10
30 -20 -10 0

% java ThreeSum [Link] -40 40 0 0

4
-10 0 10 0
4

Context. Deeply related to problems in computational geometry.

11
8

1
2
3

 3-SUM: brute-force algorithm

public class ThreeSu

public static int count(int[] a

int N = [Link]
int count = 0
check each triple
for (int i = 0; i < N; i++)
for simplicity, ignore
for (int j = i+1; j < N; j++
integer over ow
for (int k = j+1; k < N; k++
if (a[i] + a[j] + a[k] == 0
count++
return count

public static void main(String[] args

In in = new In(args[0])
int[] a = [Link]() 12
{

fl
;

Measuring the running time

Q. How to time a program? % java ThreeSum [Link]

A. Manual. tick tick tick

70
% java ThreeSum [Link]

tick tick tick tick tick tick tick tick

tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick

528
% java ThreeSum [Link]
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
tick tick tick tick tick tick tick tick
4039

Observing the running time of a program 13

 Measuring the running time

Q. How to time a program?

A. Automatic.

public class Stopwatch (part of [Link] )

Stopwatch() create a new stopwatch

double elapsedTime() time since creation (in seconds)

public static void main(String[] args

In in = new In(args[0])
int[] a = [Link]()
Stopwatch stopwatch = new Stopwatch();
client code
[Link]([Link](a))
double time = [Link]()
[Link]("elapsed time " + time)
} 14
{

Empirical analysis

Run the program for various input sizes and measure running time.

15
Empirical analysis

Run the program for various input sizes and measure running time.

N time (seconds) †

250 0

500 0

1,000 0.1

2,000 0.8

4,000 6.4

8,000 51.1

16,000 ?

16
Data analysis

Standard plot. Plot running time T (N) vs. input size N.

standard plot 50 log-log plot 51.2 s

25.6

40 12.8
running time T(N)
6.4

lg(T(N))
30 3.2

1.6

20 .8

.4

10 .2

.1

1K 2K 4K 8K 1
problem size N
Analysis of experimental data (the running time of ThreeSum)

17
analysis
Log-log plot. Plot running time T (N) vs. input size N using log-log scale
log-log plot 51.2 straight line
of slope 3
25.6

12.8 lg(T (N)) = b lg N + c

lg(T(N)) 6.4 b = 2.999
3.2 c = -33.2103
1.6

.8
T (N) = a N b, where a = 2 c
.4
3 order
of magnitude .2

.1

8K 1K 2K 4K 8K
lg N
ental data (the running time of ThreeSum)
power law

slope

Regression. Fit straight line through data points: a N b

Hypothesis. The running time is about 1.006 × 10 –10 × N 2.999 seconds. 18
s

Prediction and validation

Hypothesis. The running time is about 1.006 × 10 –10 × N 2.999 seconds

"order of growth" of running

time is about N3 [stay tuned]
Predictions
51.0 seconds for N = 8,000
408.1 seconds for N = 16,000

Observations.
N time (seconds) †

8,000 51.1

8,000 51

8,000 51.1

16,000 410.8

validates hypothesis!

19
.

Doubling hypothesis

Doubling hypothesis. Quick way to estimate b in a power-law relationship

Run program, doubling the size of the input

N time (seconds) † ratio lg ratio

T (2N ) a(2N )b
=
250 0 – T (N ) aN b
= 2b
500 0 4.8 2.3

1,000 0.1 6.9 2.8

2,000 0.8 7.7 2.9

4,000 6.4 8 3 lg (6.4 / 0.8) = 3.0

8,000 51.1 8 3

seems to converge to a constant b ≈ 3

Hypothesis. Running time is about a N b with b = lg ratio.

Caveat. Cannot identify logarithmic factors with doubling hypothesis.
20
.

Doubling hypothesis

Doubling hypothesis. Quick way to estimate b in a power-law relationship

Q. How to estimate a (assuming we know b)

A. Run the program (for a suf cient large value of N) and solve for a

N time (seconds) †

8,000 51.1
51.1 = a × 80003
8,000 51
⇒ a = 0.998 × 10 –10
8,000 51.1

Hypothesis. Running time is about 0.998 × 10 –10 × N 3 seconds.

almost identical hypothesi

to one obtained via linear regression
21
s

fi
?

Experimental algorithmics

System independent effects

Algorithm determines exponen

Input data in power law

determines constant in
System dependent effects
power law
Hardware: CPU, memory, cache,
Software: compiler, interpreter, garbage collector,
System: operating system, network, other apps,

Bad news. Dif cult to get precise measurements.

Good news. Much easier and cheaper than other sciences.

e.g., can run huge number of experiments

22
.

fi
.

 1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

Mathematical models for running time

Total running time: sum of cost × frequency for all operations

Need to analyze program to determine set of operations
Cost depends on machine, compiler
Frequency depends on algorithm, input data

Donald Knuth
1974 Turing Award

In principle, accurate mathematical models are available.

24
.

 Cost of basic operations

Challenge. How to estimate constants.

operation example nanoseconds †

integer add a+b 2.1

integer multiply a*b 2.4

integer divide a/b 5.4

oating-point add a+b 4.6

oating-point multiply a*b 4.2

oating-point divide a/b 13.5

sine [Link](theta) 91.3

arctangent Math.atan2(y, x) 129

... ... ...

† Running OS X on Macbook Pro 2.2GHz with 2GB RAM

25
fl
fl
fl
Cost of basic operations

Observation. Most primitive operations take constant time.

operation example nanoseconds †

variable declaration int a c1

assignment statement a=b c2

integer compare a<b c3

array element access a[i] c4

array length [Link] c5

1D array allocation new int[N] c6 N

2D array allocation new int[N][N] c7 N 2

Caveat. Non-primitive operations often take more than constant time.

novice mistake: abusive string concatenation

26
Example: 1-SUM

Q. How many instructions as a function of input size N ?

int count = 0
for (int i = 0; i < N; i++
if (a[i] == 0
count++;

N array accesses

operation frequency

variable declaration 2

assignment statement 2

less than compare N+1

equal to compare N

array access N

increment N to 2 N

27
;

Example: Frequency Count - SUM IN A ARRAY

28
Example: Frequency Count - SUM IN A 2D ARRAY

29
Example: Frequency Count - Multiplication IN A 2D ARRAY

30
Example: 2-SUM

Q. How many instructions as a function of input size N

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
if (a[i] + a[j] == 0)
count++;
1
0 + 1 + 2 + . . . + (N 1) = N (N 1)
2 ⇥
Pf. [ n even] N
=
2

1 2 1
0 + 1 + 2 + . . . + (N 1) = N N
2 2
half of square half of
31
;

String theory in nite sum

1
1 + 2 + 3 + 4 + ... =
12

[Link]
32
fi
Example: 2-SUM

Q. How many instructions as a function of input size N

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
if (a[i] + a[j] == 0)
count++;
1
0 + 1 + 2 + . . . + (N 1) = N (N 1)
2 ⇥
N
=
2
operation frequency

variable declaration N+2

assignment statement N+2

less than compare ½ (N + 1) (N + 2)

equal to compare ½ N (N − 1)
tedious to count exactly
array access N (N − 1)

increment ½ N (N − 1) to N (N − 1)

33
;

Simplifying the calculations

“ It is convenient to have a measure of the amount of work involved

in a computing process, even though it be a very crude one. We may
count up the number of times that various elementary operations are
applied in the whole process and then given them various weights.
We might, for instance, count the number of additions, subtractions,
multiplications, divisions, recording of numbers, and extractions
of figures from tables. In the case of computing with matrices most
of the work consists of multiplications and writing down numbers,
and we shall therefore only attempt to count the number of
multiplications and recordings. ” — Alan Turing

ROUNDING-OFF ERRORS IN MATRIX PROCESSES

By A. M. TURING
{National Physical Laboratory, Teddington, Middlesex)
[Received 4 November 1947]
SUMMARY
A number of methods of solving sets of linear equations and inverting matrices
are discussed. The theory of the rounding-off errors involved is investigated for
some of the methods. In all cases examined, including the well-known 'Gauss
elimination process', it is found that the errors are normally quite moderate: no
exponential build-up need occur.
Included amongst the methods considered is a generalization of Choleski's method
which appears to have advantages over other known methods both as regards
accuracy and convenience. This method may also be regarded as a rearrangement
of the elimination process. 34
Downlo

THIS paper contains descriptions of a number of methods for solving sets

Simpli cation 1: cost model

Cost model. Use some basic operation as a proxy for running time

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
if (a[i] + a[j] == 0
count++;
1
0 + 1 + 2 + . . . + (N 1) = N (N 1)
2 ⇥
N
=
2
operation frequency

variable declaration N+2

assignment statement N+2

less than compare ½ (N + 1) (N + 2)

equal to compare ½ N (N − 1)

array access N (N − 1) cost model = array accesses

increment ½ N (N − 1) to N (N − 1) (we assume compiler/JVM do not

optimize any array accesses away!)
35
fi
;

 Simpli cation 2: tilde notation

Estimate running time (or memory) as a function of input size N

Ignore lower order terms
– when N is large, terms are negligibl
– when N is small, we don't car
N 3/6

Ex 1 ⅙ N 3 + 20 N + 1 ~ ⅙N
166,666,667 N 3/6 ! N 2/2 + N /3
Ex 2 ⅙ N 3 + 100 N 4/3 + 5 ~ ⅙N
Ex 3 ⅙N3 - ½N 2 + ⅓ ~ ⅙N 166,167,000

N 1,000
discard lower-order terms Leading-term approximation
(e.g., N = 1000: 166.67 million vs. 166.17 million)

Technical de nition. f(N) ~ g(N) means

36
3

.
.
.
fi
fi
.

6
e

N
6
e

Simpli cation 2: tilde notation

Estimate running time (or memory) as a function of input size N

Ignore lower order terms
– when N is large, terms are negligibl
– when N is small, we don't car

operation frequency tilde notation

variable declaration N+2 ~N

assignment statement N+2 ~N

less than compare ½ (N + 1) (N + 2) ~½N2

equal to compare ½ N (N − 1) ~½N2

array access N (N − 1) ~N2

increment ½ N (N − 1) to N (N − 1) ~ ½ N 2 to ~ N 2

37
fi
.

Example: 2-SUM

Q. Approximately how many array accesses as a function of input size N

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
"inner loop"
if (a[i] + a[j] == 0
count++;
1
0 + 1 + 2 + . . . + (N 1) = N (N 1)
2 ⇥
N
=
2

A. ~ N 2 array accesses.

Bottom line. Use cost model and tilde notation to simplify counts.
38
;

Example: 3-SUM

Q. Approximately how many array accesses as a function of input size N

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
for (int k = j+1; k < N; k++ "inner loop"
if (a[i] + a[j] + a[k] == 0
count++;

⇥
N N (N 1)(N 2)
=
3 3!
A. ~ ½ N 3 array accesses. 1 3
⇥ N
6

Bottom line. Use cost model and tilde notation to simplify counts.
39
;

Diversion: estimating a discrete sum

Q. How to estimate a discrete sum

A1. Take a discrete mathematics course
A2. Replace the sum with an integral, and use calculus

N ⇥ N
1 2
Ex 1. 1 + 2 + … + N. i x dx N
i=1 x=1 2

N N
k k 1
Ex 2. 1k + 2k + … + N k. i x dx N k+1
i=1 x=1 k+1

N ⇥
1 N
1
Ex 3. 1 + 1/2 + 1/3 + … + 1/N. dx = ln N
i=1
i x=1 x

N N N ⇥ ⇥ ⇥
N N N
1 3
Ex 4. 3-sum triple loop. 1 dz dy dx N
i=1 j=i k=j x=1 y=x z=y 6

40

Estimating a discrete sum

Q. How to estimate a discrete sum

A1. Take a discrete mathematics course
A2. Replace the sum with an integral, and use calculus

Ex 4. 1 + ½ + ¼ + ⅛ + …
i
1
= 2
i=0
2

x
1 1
dx = 1.4427
x=0 2 ln 2

Caveat. Integral trick doesn't always work!

41
?

Estimating a discrete sum

Q. How to estimate a discrete sum

A3. Use Maple or Wolfram Alpha

[Link]

[wayne:[Link]] > maple15

|\^/| Maple 15 (X86 64 LINUX
._|\| |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 201
\ MAPLE / All rights reserved. Maple is a trademark o
<____ ____> Waterloo Maple Inc
| Type ? for help
> factor(sum(sum(sum(1, k=j+1..N), j = i+1..N), i = 1..N))

N (N - 1) (N - 2
----------------
6
42
.

Mathematical models for running time

In principle, accurate mathematical models are available.

In practice
Formulas can be complicated
Advanced mathematics might be required
Exact models best left for experts

costs (depend on machine, compiler)

TN = c1 A + c2 B + c3 C + c4 D + c5 E
A = array access
B = integer add
frequencie
C = integer compare
(depend on algorithm, input)
D = increment
E = variable assignment

Bottom line. We use approximate models in this course: T(N) ~ c N 3.

43
s

 1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

 Common order-of-growth classi cations

De nition. If f (N) ~ c g(N) for some constant c > 0, then the order of growth
of f (N) is g(N)
Ignores leading coef cient
Ignores lower-order terms.

Ex. The order of growth of the running time of this code is N 3

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
for (int k = j+1; k < N; k++
if (a[i] + a[j] + a[k] == 0
count++;

Typical usage. With running times.

where leading coef cien
depends on machine, compiler, JVM, ... 45
fi
;

fi
.

fi
)

fi
.

 time
Common order-of-growth classi cations
200T

Good news. The set of functions

100T
1, log N, N, N log N, N 2, N 3, and 2N logarithmic
constant
suf ces to describe the order of growth of most common algorithms.
100K 200K 500K
size

log-log plot
512T
exponential

tic

ic
cubi

hm
dra

r
rit

ea
qua

ea

lin
lin
64T
time

8T

4T

2T
logarithmic
T
constant

1K 2K 4K 8K size 512K

Typical orders of growth

46
fi
fi

 Common order-of-growth classi cations

order of
name typical code framework description example T(2N) / T(N)
growth

add two
1 constant a = b + c; statement 1
numbers

while (N > 1)
log N logarithmic divide in half binary search ~1
{ N = N / 2; ... }

for (int i = 0; i < N; i++ nd the

N linear loop 2
{ ... } maximum

divid
N log N linearithmic [see mergesort lecture] mergesort ~2
and conquer

for (int i = 0; i < N; i++

N2 quadratic for (int j = 0; j < N; j++ double loop check all pairs 4
{ ... }
for (int i = 0; i < N; i++
for (int j = 0; j < N; j++ check all
N 3 cubic triple loop 8
for (int k = 0; k < N; k++ triples
{ ... }

exhaustiv check all

2N exponential [see combinatorial search lecture] T(N)
search subsets

47
fi
e

fi
 Example 1: Common order-of-growth classi cations

order of
name typical code framework description example T(2N) / T(N)
growth

add two
1 constant a = b + c; statement 1
numbers

while (N > 1)
log N logarithmic divide in half binary search ~1
{ N = N / 2; ... }

for (int i = 0; i < N; i++ nd the

N linear loop 2
{ ... } maximum

divid
N log N linearithmic [see mergesort lecture] mergesort ~2
and conquer

for (int i = 0; i < N; i++

N2 quadratic for (int j = 0; j < N; j++ double loop check all pairs 4
{ ... }
for (int i = 0; i < N; i++
for (int j = 0; j < N; j++ check all
N 3 cubic triple loop 8
for (int k = 0; k < N; k++ triples
{ ... }

exhaustiv check all

2N exponential [see combinatorial search lecture] T(N)
search subsets

48
fi
e

fi
Example 1: Common order-of-growth classi cations

Time: f(n) = 2n + 3
Space: f(n) = n + 3

49
fi
Example 2: Common order-of-growth classi cations

1
n+1

Time: f(n) = 2n + 2
Space: f(n) = n + 2

50
fi
Example 3: Common order-of-growth classi cations

n+1

n/2

Time: f(n) = n/2

51
fi
Example 4: Common order-of-growth classi cations

n+1

n x (n+1)

n xn

Time: f(n) = n2

52
fi
Example 5: Common order-of-growth classi cations

i j No. Of times

0 0 0

1 0,1 1

2 0,1,2 2

3 0,1,2,3 3

f(n) = 1+2+3+…..+n = n(n+1)/2

53
fi
Example 6: Common order-of-growth classi cations

i p
1 0+1
2 1+2
3 1+2+3
4 1+2+3+4
- -
- -
k 1+2+3+4+…

At p > n loop will break

k(k+1)/2 >

k2 >

1/2
k > (n)

54
n

fi
Example 7: Common order-of-growth classi cations

55
fi
Example 8: Common order-of-growth classi cations

56
fi
Example 9: Common order-of-growth classi cations

57
fi
Example 10: Common order-of-growth classi cations

58
fi
Example 12: Common order-of-growth classi cations

59
fi
Example 13: Common order-of-growth classi cations

60
fi
Example 14: Common order-of-growth classi cations

61
fi
Example 15: Common order-of-growth classi cations

62
fi
Example 16: Common order-of-growth classi cations

63
fi
Example 17: Common order-of-growth classi cations

64
fi
Example 18: Common order-of-growth classi cations

65
fi
Example 20: Common order-of-growth classi cations

66
fi
Example 21: Common order-of-growth classi cations 2-SUM

int count = 0
for (int i = 0; i < N; i++
for (int j = i+1; j < N; j++
if (a[i] + a[j] == 0
count++;

67
;

fi
 Binary search demo

Goal. Given a sorted array and a key, nd index of the key in the array

Binary search. Compare key against middle entry

Too small, go left
Too big, go right
Equal, found.

successful search for 33

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi

68
.

fi
.

 Binary
Trivialsearch: Java implementation
to implement
First binary search published in 1946
First bug-free one in 1962
Bug in Java's [Link]() discovered in 2006.

public static int binarySearch(int[] a, int key

int lo = 0, hi = [Link]-1
while (lo <= hi

int mid = lo + (hi - lo) / 2

if (key < a[mid]) hi = mid - 1 one "3-way compare"

else if (key > a[mid]) lo = mid + 1

else return mid

return -1
}
Invariant. If key appears in the array a[], then a[lo] ≤ key ≤ a[hi].
69
{

 Binary search: mathematical analysis

Proposition. Binary search uses at most 1 + lg N key compares to search in a

sorted array of size N.

Def. T (N) = # key compares to binary search a sorted subarray of size ≤ N

Binary search recurrence. T (N) ≤ T (N / 2) + 1 for N > 1, with T (1) = 1.

left or right hal possible to implement with on

( oored division) 2-way compare (instead of 3-way)
Pf sketch. [assume N is a power of 2]

T (N) ≤ T (N / 2) + 1 [ given ]

≤ T (N / 4) + 1 + 1 [ apply recurrence to rst term ]

≤ T (N / 8) + 1 + 1 + 1 [ apply recurrence to rst term ]

≤ T (N / N) + 1 + 1 + … + 1 [ stop applying, T(1) = 1 ]

= 1 + lg N
70
fl
f

fi
fi
e

 An N2 log N algorithm for 3-SUM

Algorithm. inpu
30 -40 -20 -10 40 0 10 5
Step 1: Sort the N (distinct) numbers
Step 2: For each pair of numbers a[i] sor

and a[j], binary search for -(a[i] + a[j]) -40 -20 -10 0 5 10 30 40

binary searc

(-40, -20) 60
Analysis. Order of growth is N 2 log N.
(-40, -10) 50
Step 1: N 2 with insertion sort (-40, 0) 4
Step 2: N 2 log N with binary search (-40, 5) 35

(-40, 10) 3

⋮ ⋮
Remark. Can achieve N 2 by modifying (-20, -10) 3
binary search step. ⋮ ⋮ only count i
a[i] < a[j] < a[k
(-10, 0) 1
to avoi
⋮ ⋮ double counting

( 10, 30) -4
71
( 10, 40) -50
t

Comparing programs

Hypothesis. The sorting-based N 2 log N algorithm for 3-SUM is signi cantly faster in
practice than the brute-force N 3 algorithm

N time (seconds) N time (seconds)

1,000 0.1 1,000 0.14

2,000 0.8 2,000 0.18

4,000 6.4 4,000 0.34

8,000 51.1 8,000 0.96

[Link] 16,000 3.67

32,000 14.88

64,000 59.16

[Link]

Guiding principle. Typically, better order of growth ⇒ faster in practice.

72
.

fi
 1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

Types of analyses

Best case. Lower bound on cost

Determined by “easiest” input
Provides a goal for all inputs.

Worst case. Upper bound on cost

Determined by “most dif cult” input
Provides a guarantee for all inputs.
this course

Average case. Expected cost for random input

Need a model for “random” input
Provides a way to predict performance

Ex 1. Array accesses for brute-force 3-SUM. Ex 2. Compares for binary search

Best: ~ ½ N3 Best: ~ 1
Average: ~ ½ N3 Average: ~ lg N
Worst: ~ ½ N3 Worst: ~ lg N

74

fi
.

 Theory of algorithms

Goals
Establish “dif culty” of a problem
Develop “optimal” algorithms.

Approach.
Suppress details in analysis: analyze “to within a constant factor.
Eliminate variability in input model: focus on the worst case

Upper bound. Performance guarantee of algorithm for any input

Lower bound. Proof that no algorithm can do better
Optimal algorithm. Lower bound = upper bound (to within a constant factor).

75
.

fi
.

 Commonly-used notations in the theory of algorithms

notation provides example shorthand for used to

½ N2
asymptotic 10 N 2 classif
Big Theta Θ(N2)
order of growth 5 N 2 + 22 N log N + 3 algorithms
⋮

10 N 2
100 N develo
Big Oh Θ(N2) and smaller O(N2)
22 N log N + 3 N upper bounds
⋮

½N2
N5 develo
Big Omega Θ(N2) and larger Ω(N2)
N 3 + 22 N log N + 3 N lower bounds
⋮
y

 Theory of algorithms: example 1

Goals
Establish “dif culty” of a problem and develop “optimal” algorithms
Ex. 1-SUM = “Is there a 0 in the array? ”

Upper bound. A speci c algorithm

Ex. Brute-force algorithm for 1-SUM: Look at every array entry
Running time of the optimal algorithm for 1-SUM is O(N).

Lower bound. Proof that no algorithm can do better

Ex. Have to examine all N entries (any unexamined one might be 0)
Running time of the optimal algorithm for 1-SUM is Ω(N).

Optimal algorithm.
Lower bound equals upper bound (to within a constant factor)
Ex. Brute-force algorithm for 1-SUM is optimal: its running time is Θ(N).

77
.

fi

fi
.

 Theory of algorithms: example 2

Goals
Establish “dif culty” of a problem and develop “optimal” algorithms
Ex. 3-SUM.

Upper bound. A speci c algorithm

Ex. Brute-force algorithm for 3-SUM
Running time of the optimal algorithm for 3-SUM is O(N 3).

78
.

fi
fi
.

 Theory of algorithms: example 2

Goals
Establish “dif culty” of a problem and develop “optimal” algorithms
Ex. 3-SUM.

Upper bound. A speci c algorithm

Ex. Improved algorithm for 3-SUM
Running time of the optimal algorithm for 3-SUM is O(N 2 log N ).

Lower bound. Proof that no algorithm can do better

Ex. Have to examine all N entries to solve 3-SUM
Running time of the optimal algorithm for solving 3-SUM is Ω(N ).

Open problems.
Optimal algorithm for 3-SUM
Subquadratic algorithm for 3-SUM
Quadratic lower bound for 3-SUM?
79
.

fi

fi
?

 Algorithm design approach

Start
Develop an algorithm
Prove a lower bound.

Gap?
Lower the upper bound (discover a new algorithm)
Raise the lower bound (more dif cult).

Golden Age of Algorithm Design.

1970s‑
Steadily decreasing upper bounds for many important problems
Many known optimal algorithms.

Caveats.
Overly pessimistic to focus on worst case
Need better than “to within a constant factor” to predict performance.
80
.

fi
?

 Commonly-used notations in the theory of algorithms

notation provides example shorthand for used to

10 N 2
provid
Tilde leading term ~ 10 N2 10 N 2+ 22 N log N
approximate model
10 N 2+ 2 N + 37

½ N2
asymptotic classif
Big Theta Θ(N2) 10 N 2
order of growth algorithms
5N 2+ 22 N log N + 3N

10 N 2
develo
Big Oh Θ(N2) and smaller O(N2) 100 N
upper bounds
22 N log N + 3 N

½N2
develo
Big Omega Θ(N2) and larger Ω(N2) N 5
lower bounds
N 3 + 22 N log N + 3 N

Common mistake. Interpreting big-Oh as an approximate model

This course. Focus on approximate models: use Tilde-notation
81
e

 1.4 A NALYSIS OF

‣ introductio
‣ observation
‣ mathematical model
Algorithms
‣ order-of-growth classi cation
‣ theory of algorithm
R OBERT S EDGEWICK | K EVIN W AYNE

[Link] ‣ memory
n

fi
s

Basics

Bit. 0 or 1 NIST most computer scientists

Byte. 8 bits
Megabyte (MB). 1 million or 220 bytes
Gigabyte (GB). 1 billion or 230 bytes

64-bit machine. We assume a 64-bit machine with 8-byte pointers

Can address more memory
Pointers use more space. some JVMs "compress" ordinary objec
pointers to 4 bytes to avoid this cost

83
.

 Typical memory usage for primitive types and arrays

type bytes type bytes

boolean 1 char[] 2 N + 24

byte 1 int[] 4 N + 24

char 2 double[] 8 N + 24

int 4 one-dimensional arrays

oat 4

long 8
type bytes
double 8
char[][] ~2MN
primitive types

int[][] ~4MN

double[][] ~8MN

two-dimensional arrays

84
fl
Typical memory usage for objects in Java

Object overhead. 16 bytes

integer wrapper object 24 bytes
Reference. 8 bytes.
public class Integer
Padding.
{ Each object uses a multiple of 8 bytes
private int x; object
... overhead
}
x int
value
Ex 1. A Date object uses 32 bytes of memory.
padding

date object 32 bytes

public class Date
{
private int day; object 16 bytes (object overhead)
private int month; overhead
private int year;
...
} day 4 bytes (int)
month int 4 bytes (int)
year values
4 bytes (int)
padding 4 bytes (padding)

32 bytes

counter object 32 bytes

public class Counter 85
.

Typical memory usage summary

Total memory usage for a data type value

Primitive type: 4 bytes for int, 8 bytes for double,
Object reference: 8 bytes
Array: 24 bytes + memory for each array entry
Object: 16 bytes + memory for each instance variable
Padding: round up to multiple of 8 bytes
+ 8 extra bytes per inner class objec
(for reference to enclosing class)

Shallow memory usage: Don't count referenced objects

Deep memory usage: If array entry or instance variable is a reference

count memory (recursively) for referenced object.

86
t

 Example

Q. How much memory does WeightedQuickUnionUF use as a function of N

Use tilde notation to simplify your answer

16 byte
public class WeightedQuickUnionU
(object overhead)

8 + (4N + 24) bytes eac

private int[] id
(reference + int[] array)
private int[] sz 4 bytes (int)
private int count 4 bytes (padding)

8N + 88 bytes
public WeightedQuickUnionUF(int N

id = new int[N]
sz = new int[N]
for (int i = 0; i < N; i++) id[i] = i
for (int i = 0; i < N; i++) sz[i] = 1;

A. 8 N + 88 ~ 8 N bytes.
87
{

Turning the crank: summary

Empirical analysis
Execute program to perform experiments
Assume power law and formulate a hypothesis for running time
Model enables us to make predictions

Mathematical analysis
Analyze algorithm to count frequency of operations
Use tilde notation to simplify analysis
Model enables us to explain behavior

Scienti c method
Mathematical model is independent of a particular system;
applies to machines not yet built
Empirical analysis is necessary to validate mathematical models
and to make predictions.

88
fi
.