Analysis of Algorithms

October 14, 2020

An introduction to the rigorous analysis of algorithms using empirical methods and theoretical models

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 N2N^2
    • FFT algorithm NlogNN \log{N} steps, enables new technology

N-body Simulation

  • Simulate gravitational interactions among N bodies

    • Brute force: N2N^2
    • Barnes-Hut algorithm NlogNN \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 log-log

logT(N)=blogN+cT(N)=aNb\log{T(N)} = b \log{N} + c \\ T(N) = a N^b

where a=2ca = 2^c

Hypothesis: The running time is about 1×1010N2.9991 \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 power-law 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.

1-Sum

An extremely simple variant of 3-Sum

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
Two-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++
Operation Frequency
variable declaration N+2
assignment statement N+2
less than comparison 12(N+1)(N+2)\frac{1}{2} (N + 1) (N+2)
equal to compare 12N(N1)\frac{1}{2} N(N-1)
array access N(N+1)N(N + 1)
increment 12N(N+1)\frac{1}{2} N(N + 1) to N(N+1)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

16N3+16\frac{1}{6} N^3 + 16 16N3\sim \frac{1}{6} N^3
16N3+100N4/3+56\frac{1}{6} N^3 + 100 N^{4/3} + 56 16N3\sim \frac{1}{6} N^3
16N312N2+3N\frac{1}{6} N^3 - \frac{1}{2}N^2 + 3N 16N3\sim \frac{1}{6} N^3

f(N)g(N)f(N) \sim g(N) means “pretty much the same for large N” but more strictly:

limNinff(N)g(N)=1\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+2N+2 N\sim N
assignment N+2N+2 N\sim N
less than 12(N+1)(N+2)\frac{1}{2} (N + 1) (N+2) 12N2\sim \frac{1}{2} N^2
equal to 12N(N1)\frac{1}{2} N(N-1) 12N2\sim \frac{1}{2} N^2
array access N(N+1)N(N + 1) N2\sim N^2
increment 12N(N+1)\frac{1}{2} N(N + 1) to N(N+1)N(N + 1) 12N2\frac{1}{2} \sim N^2 to N2\sim N^2

In our 2-Sum 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

0+1+2+...+(N1)=12N(N1)=(N2)0 + 1 + 2 + ... + (N - 1) = \frac{1}{2} N (N - 1) = {N \choose 2}

We will have N2\sim N^2 array accesses

This notation helps us take apart the more complicated original version, 3-Sum

//...
if (a[i] + a[j] + a[k] == 0)
//...
(N3)=N(N1)(N2)3!16N3{N \choose 3} = \frac{N(N-1)(N-2)}{3!} \sim \frac{1}{6} N^3

We will have N3\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,logN,N,NlogN,N2,N3,2N1, 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 order-of-growth)

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 sorting-based algorithm for 3-Sum such that we yield a N2logNN^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]a[i] < a[j] a[k]

Analysis

  • Step 1: N2N^2 with insertion sort
  • Step 2: N2logNN^2 \log N

In practice, N2logNN^2 log N is much better than N3N^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.

Back to Notes