Content is adapted from lecture notes of Sedgewick’s ‘Algorithms (4th Ed.)’
As soon as an Analytical Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will then arise by what course of calculation can these results be arrived at by the machine in the shortest time?
— Charles Babbage
We are going to explore and classify algorithms by seeing how they consume computing resources.
Reasons to analyze algorithms
 Predict performance
 Compare algorithms
 Provide guarantees
 Understand theoretical basis
Primary practical reasons: avoid performance bugs
Discrete Fourier Transform
 Breakdown waveform of N samples in to periodic components

Applications: DVD, JPEG, MRI, Astrophysics
 Brute force $N^2$
 FFT algorithm $N \log{N}$ steps, enables new technology
Nbody Simulation

Simulate gravitational interactions among N bodies
 Brute force: $N^2$
 BarnesHut algorithm $N \log{N}$ steps, enables new research
Scientific method
Observations
Make some observations about running time.
In algorithms analysis, observing the running time is easier than systematic study in many other disciplines.
3—Sum problem Given N distinct integers, how many triples sum to exactly zero?
$ cat eightNumbers.txt
30 40 20 10 40 0 10 5
$ java ThreeSum eightNumbers.txt
4
Where
a[i] 
a[j] 
a[k] 
Sum 

30  40  10  0 
30  20  10  0 
40  40  0  0 
10  0  10  0 
Brute force algorithm
public class ThreeSum {
public state int count(int[] a) {
int N = a.length;
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++;
return count;
}
public state void main(String[] args) {
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
Empirically you can determining the run time of an algorithm by grabbing a clock and seeing how long it runs. Java offers a standard stopwatch utility. By feeing in systematically larger and larger input you can watch the runtime grow for each execution and plot the data.
8ints, 1Kints, 2Kints, 4Kints, 8Kints, 16Kints
Plot the result with loglog
$\log{T(N)} = b \log{N} + c \\ T(N) = a N^b$where $a = 2^c$
Hypothesis: The running time is about $1 \times 10^{10} N^{2.999}$
With this, you can then make predictions about run time without running the program.
Subsequent observations can validate that hypothesis.
Doubling hypothesis: Quick way to estimate b in a powerlaw relationship
Run the program doubling the size of the input
Caveat: Cannot identify logarithmic factors
Experimental algorithms
System independent effects
 Algorithm
 Input data
System dependent effects
 Hardware: CPU, memory, cache
 Software: compiler, interpreter, garbage collector
 System: operating system, network, other apps
Bad news. Difficult to get precise measurements Good news. Much easier and cheaper than other sciences (e.g. we can run a huge number of experiments)
Mathematical models
Mathematical models of run time, popularized by Donald Knuth in the late 60’s.
Computer systems at this time were becoming unfeasibly complicated to track with traditional methods. Knuth suggested mathematical models for understanding run time.
Understood as the sum of cost times the frequency for all operations
 Need to analyze program to determine set of operations
 Cost depends on machine, compiler
 Frequency depends on algorithm, input data
This work proved that in principle, accurate mathematical models are available.
How many instructions as a function of input size N?
First identify the times associated with the core operations of the language and the compiler. Start by clocking the speed of basic operations. Simple math operations like floating point multiplication will take a few nanoseconds in a modern laptop. You’ll then need to figure out the cost of logical operations like variable declaration, assignments, comparisons, and array accesses. Anything needed to evaluate an expression.
Then for some function, you will need to understand the frequency.
1Sum
An extremely simple variant of 3Sum
int count = 0;
for (int i = 0; i < N; i++)
if (a[i] == 0)
count++
Operation  Frequency 

variable declaration  2 
assignment statement  2 
less than comparison  N 
equal to compare  N 
array access  N + 1 
increment  N to 2N 
TwoSum
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++
Operation  Frequency 

variable declaration  N+2 
assignment statement  N+2 
less than comparison  $\frac{1}{2} (N + 1) (N+2)$ 
equal to compare  $\frac{1}{2} N(N1)$ 
array access  $N(N + 1)$ 
increment  $\frac{1}{2} N(N + 1)$ to $N(N + 1)$ 
This is incredibly tedious.
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
First simplification: Ignore all but the most expensive operations and/or frequent operations. Use this operation as a proxy for run time.
Second simplification: Discard lower order terms
$\frac{1}{6} N^3 + 16$  $\sim \frac{1}{6} N^3$ 
$\frac{1}{6} N^3 + 100 N^{4/3} + 56$  $\sim \frac{1}{6} N^3$ 
$\frac{1}{6} N^3  \frac{1}{2}N^2 + 3N$  $\sim \frac{1}{6} N^3$ 
$f(N) \sim g(N)$ means “pretty much the same for large N” but more strictly:
$\lim{N \to \inf} \frac{f(N)}{g(N)} = 1$We use a tilde notation to simplify the run time model
Frequency  Frequency  Notation 

declaration  $N+2$  $\sim N$ 
assignment  $N+2$  $\sim N$ 
less than  $\frac{1}{2} (N + 1) (N+2)$  $\sim \frac{1}{2} N^2$ 
equal to  $\frac{1}{2} N(N1)$  $\sim \frac{1}{2} N^2$ 
array access  $N(N + 1)$  $\sim N^2$ 
increment  $\frac{1}{2} N(N + 1)$ to $N(N + 1)$  $\frac{1}{2} \sim N^2$ to $\sim N^2$ 
In our 2Sum case, array accesses are among the most expensive and most frequent. We’ll use this as a proxy for our cost model.
//...
if (a[i] + a[j] == 0)
//...
We can see how a[j]
will run
We will have $\sim N^2$ array accesses
This notation helps us take apart the more complicated original version, 3Sum
//...
if (a[i] + a[j] + a[k] == 0)
//...
We will have $\sim N^3$ array accesses
More models
Knuth tells us
In principle, accurate models exist
But in practice,
 Formulas can be complicated
 Advanced mathematics requires
 Exact models left to the exports
The costs will depend on the machine and the compiler
The frequencies will depend on the algorithms and the input
We will use approximate models in this course
Fortunately, there’s not a lot of models that are used in practice
$1, log N, N, N log N, N^2, N^3, 2^N$These few functions suffice to describe the order of growth of typical algorithms.
(Picture of logarithmic growth curves)
(Table of order of growth classifications)
(Table on practical implications of orderofgrowth)
Mathematical analysis
Look at an old example
Let’s see how Binary Search grows
public static int binarySearch(int[] a, int key) {
int lo = 0,
hi = a.length  1;
while (lo <= hi) {
int mid = lo + (hi  lo) / 2;
if (key < a[mid]) hi = mid  1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return 1;
}
Proposition. Binary search uses at most 1 + lg N key compares to search in a sorted array of size N
If granted, this means we can incorporate a sortingbased algorithm for 3Sum such that we yield a $N^2 \log N$ algorithm.
 First sort N distinct numbers
 For each pair of numbers, binary search for
(a[i] + a[j])
For this, we only need to count the elements $a[i] < a[j] a[k]$
Analysis
 Step 1: $N^2$ with insertion sort
 Step 2: $N^2 \log N$
In practice, $N^2 log N$ is much better than $N^3$.
Goals. ・Establish “difficulty” of a problem. ・Develop “optimal” algorithms.Approach. ・Suppress details in analysis: analyze “to within a constant factor”. ・Eliminate variability in input model by focusing on the worst case.Optimal algorithm. ・Performance guarantee (to within a constant factor) for any input ・No algorithm can provide a better performance guarantee.
Start. ・Develop an algorithm. ・Prove a lower bound.Gap? ・Lower the upper bound (discover a new algorithm). ・Raise the lower bound (more difficult). 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.