Preview lessons, content and tests

Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.
2. Searching for something specific? See our text overview of all tests. Scroll right for levels, and lists.

Student and Teacher User Guides |   Schemes of Work |   Real Teacher use Videos |

Join 30000+ teachers and students using TTIO.

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)

www.teachyourselfpython.com