Lecture notes for CS 509, Advanced Programming II

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

n² 10,000

n³ 1,000,000

2ⁿ 1,267,650,600,228,229,401,496,703,205,376

f	f(n)
C	C
log n	4.6
n	100
n log n	460.5
n²	10,000
n³	1,000,000
2ⁿ	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 s₁ else s₂
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 24 February 2003.