Computer Algorithms II Lecture Notes

2 October 2007 • Performance Estimation

Outline

• Algorithms and Programs

  • Algorithm Analysis

  • Measuring Algorithm Performance

  • Estimated Performance Analysis

• Asymptotic Estimates

• A Behavior Hierarchy

• Structural Analysis

  • Statements

  • Statement Sequence

  • Loops

  • If Statements

  • Subroutines

A Program

string read

while getline(cin, str)
  read += str

for i = 0 to read.size()
  if read[i] == '<'
    // process tag

• Read in a string, then process all tags.

Another Program

string read

while getline(cin, str)
  read += str
  for i = 0 to read.size()
    if read[i] == '<'
      // process tag
      read[i] = ' '

• Likewise: read in a string, then process all tags.

• Which program is better?

Making Choices

• There are lots of data structures and algorithms to choose from.

  • There are lots of data structures and algorithms of the same kind.

• How do you decide among them?

  • How do you make a good decision?

Measuring Performance

• Measure execution time, or storage, or ...

• It's a definitive measure.

• But

  • Measurements are context dependent.

    • Determining context accurately is difficult.

  • Comparing results is hard.

    • Contexts must match to be meaningful.

Estimating Performance

• If you don't know, guess (or estimate).

  • Ignore the details, go for the big picture.

  • Estimating is simpler than measuring.

• Estimates are more comparable then are measurements.

  • Estimating uses minimal context.

• Estimates are more durable than are measurements.

  • Not tied to particular hardware or software.

• Skillful professionals estimate well.

  • Estimation is a skill to develop.

Estimating Algorithms

• How do you estimate algorithms?

  • Algorithms are abstract, and they don't execute.

• Simulate execution by counting something happening during pretend execution.

  How many times is the loop body executed if the input contains 17 items?

• Algorithm details are reduced to a function.

Modeling Algorithms

• Model the algorithm as a function f(n).

  • f(n) is the estimated algorithm behavior for an input of size n.

  • What can n represent?

    • Whatever's important: bits, lines, records.

  • What can f(n) represent?

    • Whatever's important: behavior in time or space, messages, errors, dollars.

Sorting Model Example

• Model a sorting algorithm with the function f(n) where

  • n is the number of elements being sorted.

  • f(n) is the time used to sort n elements.

  • or f(n) is number of comparisons made when sorting n elements.

  • or f(n) is number of swaps made when sorting n elements.

  • or...

Database Model Example

• Model a distributed-database algorithm with the function f(n) where

  • n is the number of machines over which the database is distributed.

  • Or n is the percentage of machines that can satisfy a query.

  • f(n) is the number of messages it takes to perform a transaction.

  • Or f(n) is amount of time it takes to commit a transaction.

Estimating Functions

• After turning an algorithm into f(n), estimate f(n)'s behavior.

  • There are many ways to estimate f(n)'s behavior.

• An upper bound on f(n)'s behavior is useful.

  • It represents potential worst-case behavior.

  • Other bounds are possible, but harder to find.

Upper Bounds

• Suppose that, for most values of n, f(n) ≤ g(n).

  • g(n) is an upper bound to f(n).

• It's an asymptotic estimate because n grows without bound.

• An alternative representation for f(n)'s upper bound is O(g)

  • That is, f(n) = O(g).

Asymptotic Estimate Properties

• Larger estimates swallow up smaller estimates.

  • O(f) + O(g) is O(max(f, g)).

  • An upper bound for the larger is an upper bound for the smaller.

• The product of estimates is the estimate of the product.

  • O(f)*O(g) = O(fg).

Tight Estimates

• Suppose f = O(g) and f = O(h).

  • If g = O(h), then g is a tighter estimate of f than is h.

    

• The tighter of two estimates is the better one.

A Behavior Hierarchy

• A hierarchy of function behavior.

  Constant	O(1)	array index
  Log	O(log n)	binary search
  Linear	O(n)	linear search
  Log-linear	O(n log n)	heapsort
  Quadratic, square	O(n2)	bubble sort

• Higher in the hierarchy is better (asymptotically faster).

Constant Behavior

Logarithmic Behavior

• This is repeated division behavior.

Linear Behavior

• This is "touch every element" behavior.

Log-Linear Behavior

• This is sorting behavior.

• Repeatedly divide for every element.

Quadratic Behavior

• This is double loop behavior.

A Family Portrait

• Let n = 100.

  f f(n) C C log n 6.6 n 100 n log n 664.4 n2 10,000		Improving asymptotic behavior is important. Move to the next lowest level of asymptotic behavior.

• Don't fiddle with the code, fiddle with the algorithm.

Structural Analysis

• Algorithms have a regular structure.

  • Statements, sequences, loops, and choice.

• Use program structure to derive asymptotic estimates.

  • Assign behavior to smaller units.

  • Combine units following algorithm structure to find behavior of larger units.

  • Repeat until the whole algorithm's been combined into a single estimate.

A Running Example

• Bubble sort.

  i = 0
  while i < n
    j = i + 1
    while j < n
      if a[i] > a[h]
        swap(a[i], a[j])
      j++
    i++
  

Statements

• Usually O(1), but know your data structures.

• Estimate the simple statements.

  i = 0 while i < n j = i + 1 while j < n if a[i] > a[h] swap(a[i], a[j]) j++ i++

  O(1) while i < n O(1) while j < n if a[i] > a[h] O(1) O(1) O(1)

if statement

• if b s1 else s2

• Execute either s₁ or s₂, but which one?

  • Because we're overestimating, use the larger of the estimates.

• Don't forget b's cost.

  • O(f_b) + O(max(f₁, f₂))

Example if Estimates

• To continue:

  O(1) while i < n O(1) while j < n if a[i] > a[h] O(1) O(1) O(1)

  O(1) while i < n O(1) while j < n O(1) + O(1) = O(1) O(1) O(1)

Statement Sequence

• s₁ ; s₂

• s₁ is O(f), s₂ is O(g), so s₁; s₂ is O(f) + O(g)

• What is O(f) + O(g)?

  • Take the larger of the two.

    • O(f) + O(g) is O(max(f, g))

Example Sequence Estimates

• Continued:

  O(1) while i < n O(1) while j < n O(1) O(1) O(1)

  O(1) while i < n O(1) while j < n O(1) + O(1) = O(max(1, 1)) = O(1) O(1)

Loops

• while b do s

• s has asymptotic estimate O(f).

• s gets executed some number of times.

  • Asymptotically bound the number of times as O(g).

• The estimate is O(f)*O(g).

  • O(f)*O(g) is equivalent to O(fg)

Loop Overhead

• The loop itself does constant work per iteration.

  • Ignore it.

  • This includes the cost of evaluating b.

• An implicit, and occasionally troublesome, assumption.

  • But, it allows us to deal with for loops in the same way.

Loop Estimate Example

• Continued:

  O(1) while i < n O(1) while j < n O(1) O(1)

  O(1) while i < n O(1) O(n)*(O(1) + O(1)) = O(n)*O(max(1, 1)) = O(n)*O(1) = O(n*1) = O(n) O(1)

Finishing Up.

• Estimate the loop-body statement sequence.

  O(1) while i < n O(1) O(n) O(1)

  O(1) while i < n O(1) + O(n) + O(1) = O(max(1, n, 1) = O(n)

Finishing Up..

• Estimate the loop.

  O(1) while i < n O(n)

  O(1) O(n)*O(n) = O(n*n) = O(n2)

Finishing Up...

• Estimate the statement sequence.

  O(1) O(n2)

  O(1) + O(n2) = O(max(1, n2)) = O(n2)

• Done: O(n²)

• The structure of the algorithm determines the next step.

Subroutines

• Non-recursive subroutines are treated like a statement.

  • Guess at or know the estimate for a call.

  • swap(a, b) = O(1).

• Recursive calls are tougher.

  • Solved with recurrence relations.

  • Later for that.

Constants

• Constants are a subtle point in asymptotic analysis.

• Constants come from the mathematical definition of O().

  • For some non-negative integer N, there exists a positive real constant C such that

    f(n) ≤ Cg(n)

    for all n > N.

Constants Interpreted

• Graphically, different constants represent vertical shifts in the same graph.

  

• Smaller (lower) constants are better.

Good Constants

• Many algorithms are asymptotically equivalent.

  • Many sorting algorithms are O(n²).

• Asymptotically equivalent algorithms may have (usually have) different execution behavior.

  • The constants help characterize the difference.

• Fiddling with code usually involves reducing the constant.

Points to Remember

• Develop algorithms, not programs.

• Use performance criteria to select algorithms.

• Use asymptotic estimates for performance.

• Estimate performance using structural analysis.

• Understand what the estimates are saying.