Lecture Notes for Advanced Programming II

15 October 2002 - Asymptotic Estimates

Asymptotic Estimates

• 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

Algorithms and Programs

• Programs come from algorithms.

  • Algorithms are abstract programs.

• Algorithms are easier to work with than are programs.

  • Algorithms have less details than do programs.

  • You can concentrate on the solution and not the code.

• Good programs come from good algorithms.

  • Good programs never come from bad algorithms.

Algorithm Analysis

• There are many algorithms, all different.

• Which algorithm can be judged suitable?

  • It depends on your criteria.

  • Memory use, speed, message count, ...

• Start with performance.

  • Performance is usually related to other criteria.

    • It takes time to use a resource.

• Algorithm performance can be measured or estimated.

Measuring Algorithm Performance

• Measure execution time.

• It's a definitive measure.

• But algorithms don't execute; they're not code.

  • It requires implementing the algorithm.

• There are other problems too.

  • Measurements are context dependent.

    • Determining context accurately is difficult.

  • Comparing results is hard.

    • Contexts must match to be meaningful.

  • Meaningful measurements are hard.

Estimated Performance Analysis

• Ignore the details, go for the big picture.

  • Estimating is simpler than measuring.

• Estimates are more comparable then are measurements.

  • The context is less important.

• Estimates are more durable than are measurements.

• Skillful professionals estimate well.

  • Estimation is a skill to develop.

Asymptotic Estimates

• An upper bound on algorithm behavior - no more than.

  • Other bounds are possible, but harder.

• O(f) - an estimate no worse (larger) than f.

• Algorithm behavior as functions of input size n, other details abstracted away.

• Examine what happens as n grows large, that is, approaches infinity.

  • Hence asymptotic.

• What kind of input is expected?

  • Statements, bytes, nodes.

• What kind of output is being estimated?

  • Behavior in time or space, messages, errors, dollars.

• Details to follow in CS 512.

Manipulating Asymptotic Estimates

• Larger estimates swallow up smaller estimates.

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

  • Treat O(f) as a set of functions, pick a representative function and apply the definition of big-oh.

  • Take the larger of the two.

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

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

  • Need a function that's bigger than both.

  • How about f*g?

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

A Behavior Hierarchy

• A hierarchy of functions.

  • Constant - O(1), hash table searching

  • Log - O(log n), binary search

  • Linear - O(n), linear search

  • Log-linear - 0(n log n), heapsort

  • Quadratic, square - O(n²), bubble sort

  • Cubic - O(n³), matrix multiplication

  • Exponential - O(2ⁿ), optimal route finding

• Polynomial functions - quadratic, cubic, and so on.

• The boundary between polynomial and exponential functions.

Constant Behavior

• This is input-independent behavior

  • This is the ideal behavior.

  • But watch out for the value of C.

Logarithmic Behavior

• This is repeated dividing behavior.

  • Binary search.

Linear Behavior

• This is touch every element behavior.

Log-Linear Behavior

• This is sorting behavior.

Quadratic Behavior

• This is double loop behavior.

Cubic Behavior

• This is triple loop behavior.

  • Matrix multiplication.

Exponential Behavior

• This is systematic guessing behavior.

A Family Portrait

• Let n = 100.

  f	f(n)
  C	C
  log n	4.6
  n	100
  n log n	460.5
  n2	10,000
  n3	1,000,000
  2n	1,267,650,600,228,229,401,496,703,205,376

• Except for small n, improving asymptotic behavior is important.

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

  • Move down to the next lowest level of asymptotic behavior.

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: swap sort.

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

Statements

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

  • Compare vec.size() with lst.size().

• Estimate the simple statements.

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

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₂))

• Estimate the if statements.

  O(1)
  while i < n
    O(1)
    while j < n
      if a[i] > a[h]
        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)?

  • Treat O(f) as a set of functions, pick a representative function and apply the definition of big-oh.

  • Take the larger of the two.

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

• Estimate the statement sequences.

  O(1)
  while i < n
    O(1)
    while j < n
      O(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(f*g)

• 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.

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

To Finish

• Estimate the statement sequence.

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

• Estimate the loop

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

• Estimate the statement sequence.

  O(1)
  O(n^2)
  

• Done: O(n^2)

• 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.

• Recursive calls are tougher.

  • Solved with recurrence relations.

  • Later for that.

• Example.

  while vec.size() > 0
    vec.erase(vec.end() - 1)
  
  while vec.size() > 0
    vec.erase(vec.begin())
  

Things to Watch

• Keep an eye on the constants.

  • Asymptotically identical algorithms may be (usually are) different.

  • For small n, constants are more important - linear search is usually good enough.

• Estimate the right things.

  • What's important: an expensive algorithm, or the number of times it's called?

• Look at the right inputs.

  • Focus on what's driving the algorithm.

  • Worrying about execution time on communication-bound computations.

Points to Remember

• Develop algorithms not programs.

  • Code programs from algorithms.

• Use performance criteria to select algorithms.

  • Keep in mind other criteria.

• Use asymptotic estimates for performance.

  • Remember these are estimates.

• Estimate performance using structural analysis.

  • Let the algorithm give you the next step.

• Understand what the estimates are saying.

  • Which algorithm is the better performer.

This page last modified on 15 October 2002.