Lecture Notes for Advanced Programming II

25 February 2003 - 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 execution time.

  • Performance is usually related to other criteria.

    • It takes time to use a resource.

• Algorithm performance can be measured or estimated.

Determining 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

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

  • The context is mostly ignored when estimating.

• Estimates are more durable than are measurements.

  • Not as closely tied to hardware or software technology.

• Skillful professionals estimate well.

  • Estimation is a skill to develop.

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.

• The algorithm is reduced to a function, other details abstracted away.

• Make sure you understand what the input and output represent.

Example Algorithm Models

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

  • n is the number of elements being sorted.

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

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

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

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

Asymptotic Estimates

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

• An upper bound of f(n)'s behavior is a function g(n) with the property that
  C*g(n) >= f(n)
  as n grows without bound for some positive constant C.

  • In other words f(n) is never larger than g(n).

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

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

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

• This is only part of the story; for full details, attend CS 512.

Asymptotic Estimate Properties

• For any f(n), f(n) = O(f).

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

  • Larger estimates swallow up smaller estimates.

  • max(f, g) may not exist as n grows without bound.

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

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

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

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

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.

• Repeatedly divide for every element.

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++

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

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

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

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

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

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

To Finish

• Estimate the 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(n)

• Estimate the loop

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

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

• 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 29 October 2003.