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.
i <- 2
+-> i <= sqrt(N)? -----> output IS_PRIME
| | yes
| v yes
| does i divide N? ---> output NOT_PRIME
| | no
+--- 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
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
Source: https://www.cs.cmu.edu/ (archive adaptation)