Data Structures and Algorithms Lecture Notes

28 February 2011 • Structural Analysis

Outline

Structural Analysis

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

`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(n²)

Sequence Estimate

O(1)
O(n²)

O(1) + O(n²) = O(n²)

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

Estimate performance using structural analysis.
- Let the algorithm give you the next step.
Understand what the estimates are saying.

This page last modified on 2010 September 4.