Data Structures & Algorithms Lecture Notes

13 October 2009 • Asymptotic Estimates

---

Outline

• Algorithms and Programs

• Asymptotic Estimates

• A Behavior Hierarchy

• Structural Analysis

An Algorithm

• Algorithm 1.

  StringBuilder read
  
  while str = input.readline()
    read.append(str)
  
  for i = 0 to read.length()
    if read.charAt(i) == '<'
      // process tag
  

Another Algorithm

• Algorithm 2.

  StringBuilder read
  
  while str = input.readline()
    read.append(str)
    for i = 0 to read.length()
      if read.charAt(i) == '<'
        // process tag
        read.setCharAt(i) = ' '
  

• Which algorithm is better?

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.

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

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

Problems

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

• Skillful professionals estimate well.

  • Estimation is a skill to develop.

Estimation Advantages

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

Modeling Algorithms

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

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

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

Algorithmic Model

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

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

    • Or the number of comparisons done.

    • Or the number of elements moved.

Database Example

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

Upper-Bound Estimates

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

  • That is, f(n) is never larger than g(n).

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

Big-Oh Notation

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

Asymptotic Estimate Properties

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

Estimate Addition

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

Estimate Multiplication

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

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

Estimate Quality

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

  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		O(n2)		bubble sort
  Cubic		O(n3)		matrix multiplication
  Exponential		O(2n)		optimal route finding

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

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.

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.

Running Example

• Swap sort.

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

• Let n be the array size in elements.

• Let f(n) be the number of elements moved.

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[j] std::swap(a[i], a[j]) j++ i++

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

if Example

• Estimate the if statements.

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

Sequence Example

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

  • Work associated with iteration operations and guard testing.

• You can

  • ignore it, or

  • include it in the estimate.

• An implicit, and occasionally troublesome, assumption.

Loop Example

• Estimate the loop.

  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)

Loop Estimate

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

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

Sequence Estimate

O(1) O(n2)

O(1) + O(n2) = O(n2)

• Done: O(n²).

  In the worst case, swap sort moves O(n²) elements when sorting an n-element array.

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

Subroutine Example

• What is the estimate on each of these loops?

  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?

Further Considerations

• Look at the right inputs.

  • Focus on what’s driving the algorithm.

  • Worrying about execution time on communication-bound computations.

Summary

• Develop algorithms not programs.

  • Code programs from algorithms.

• Use performance criteria to select algorithms.

• Use asymptotic estimates for performance.

• Estimate performance using structural analysis.

  • Let the algorithm give you the next step.

• Understand what the estimates are saying.