Comparison of Algorithms

Jonathan: My algorithm is faster!

Ruth: No, mine is!

Where will this lead? Will Ruth resort to silencing Jonathan? Will Jonathan just give up? Is there any way they can settle their dispute

Approach 1: Implement and Test

Ruth and Jonathan could program their algorithms and try them out on some sample inputs.

Jonathan: But my algorithm is too complicated to implement if we're just going to throw it away!

Ruth: Maybe we'll miss some inputs on which your algorithm is bad!

Additional Character: Arf! [translation: Maybe Ruth's algorithm will look better on small test inputs, but when we get to the really big, interesting problems, Jonathan's is better.]

Additional Character #2: Doesn't this depend on which machine you use?

This isn't really a bad idea, but they have a point.

Approach 2: Graph and Extrapolate

Graph performance against problem size, and extrapolate.

     |                  .
     |     current      .
     |    computing     .
     |      power -+   .
     |     limits  |   .
     |             |  .
  ^  |             | .
  |  |             v.
time |            _~
     |           -
     |         _~
     |      _-~
     |___--~
     |
     +---------------------------
          problem size -->

Jonathan: But how do I know if the extrapolation is correct?

It would be better if we didn't treat the algorithm as a black box.

Approach 2: Create a formula

Write down the algorithm and create a formula for the running time.

  Prime-Test-All

       i <- 2
         |
         v          no
 +-> i <= sqrt(N)? -----> output IS_PRIME
 |       |
 |       | yes
 |       v           yes
 |  does i divide N? ---> output NOT_PRIME
 |       |
 |       | no
 |       v
 +--- i <- i + 1

The time consumed by Prime-Test-All for input N is at most

T[PTA](N) <= T[i <- 2] + (sqrt(N) - 1) (T[i <= sqrt(N)?] + T[i divide N?]
                                          + T[i <- i + 1]) + T[output]

Jonathan: No implementation!

Ruth: But what a mess!

Approach 3: Approximate

For really big inputs, we can ignore everything but the fastest-growing term: T[PTA](N) <= c[PTA] sqrt(N) (where c[PTA] is a constant that will change between machines).

Say Jonathan's algorithm takes T[B](N) <= c[B] sqrt(N) log_2(N) time.

For what N is Jonathan's algorithm better?

Ignore the Constants

To compare algorithms with very different bounds, we can just ignore the constants. We write T[PTA] = O(sqrt(N)) or T[B] = O(sqrt(N) log_2(N)).

This is called big-O notation.

Ruth: Aren't you simplifying a bit too much?

Yes, this is a gross simplification. But it often works!

Practice with Big-O

  50 x^2 + 25 x + 40 = O(x^2)

  5,096 log_2 n + 0.02 n = O(n)

  4,236,121 = O(1)

  4 * 2^n log_2 n + n^2 = O(2^n log_2 n)

Going from Pseudocode

  Algorithm Prime-Test-Odds(n)
  if n = 2 then return YES fi
  if n is even then return NO fi
  for each odd i such that 3 <= i <= sqrt(n) do
    if i divides n then
      return NO
    fi
  od
  return YES

  O(sqrt(n))

Source: https://www.cs.cmu.edu/ (archive adaptation)