Evaluating Algorithms

• What should we measure when comparing algorithms?
  • Correctness?
    • Important, but this class won’t focus on proofs of correctness
  • Clarity/simplicity?
    • Important, but not what we are taking about today
  • Space efficiency?
    • Yes! This is something we want to understand
  • Time Efficiency?
    • Yes! This is usually the main concern

A Story…

• I need to write Python code to find the largest gap between any pair of numbers in a list:

  def findMaxDiff(numbers):
      maxDiff = 0
      for n1 in numbers:
          for n2 in numbers:
              diff = n1 - n2
              if diff > maxDiff:
                  maxDiff = diff
      return maxDiff

Take-Home Messages (1/2)

• Analysis must account for input size
  • How does the running time change as the input size increases?

Take-Home Messages (2/2)

• Goal is to analyze algorithms, not programs
• The root problem in the story was a bad algorithm choice
• Running time of programs is subject to:
  • Programming language
  • Speed of the computer
  • Computer load
  • Compiler version
  • Implementation details
  • …
• Measuring execution time is not the most reliable way to compare two algorithms

If not time, then what?

• Number of steps that the algorithm takes to complete

• Goal: develop a function that maps from input size to the number of steps

  total = 0;
  for (int i = 0; i < numbers.length; i++) {
      total += numbers[i];
  }

  total = 0;
  for (int i = 0; i < numbers.length; i++) {
      for (int j = 0; j < numbers.length; j++) {
          total += numbers[i];
  }

Basic Operations

• Goal restated: develop a function that maps from input size to the number of basic operations
• No single correct choice for basic operation
• Any reasonable choice will give you the same answer, within a constant factor
• Guideline:
  • Should happen in inner-most loop

Socrative Quiz…

\(\log_2 1 = 0\)

\(\log_2 2 = 1\)

\(\log_2 4 = 2\)

\(\log_2 8 = 3\)

…

\(\log_2 4,000,000,000 = ??\)

1. about 6
2. about 32
3. about 1,024
4. about 10,000
5. about 1,000,000

Let’s Review Growth Functions…

Socrative Quiz…

Consider the following (very) informal definitions:

• A reasonably fast computer can perform 1,000,000,000 operations per second

• A reasonably short period of time is one second

• A program is good enough if it can process 1,000,000 items in a reasonably short period of time on a reasonably fast computer.

Assume that \(T(n)\) is a function that describes the number of operations required for program A. Select the first true statement from the following list.

1. Program A is good enough as long as \(T(n) \leq n!\)
2. Program A is good enough as long as \(T(n) \leq 2^n\)
3. Program A is good enough as long as \(T(n) \leq n^3\)
4. Program A is good enough as long as \(T(n) \leq n^2\)
5. Program A is good enough as long as \(T(n) \leq n \log n\)
6. Program A is good enough as long as \(T(n) \leq n\)
7. Program A is good enough as long as \(T(n) \leq 1\)

Socrative Quiz…

Consider the following (very) informal definitions:

• A reasonably fast computer can perform 1,000,000,000 operations per second

• A reasonably short period of time is one second

• A program is not totally useless if it can process 100 items in a reasonably short period of time on a reasonably fast computer.

Assume that \(T(n)\) is a function that describes the number of operations required for program A. Select the first true statement from the following list.

1. Program A is not totally useless as long as \(T(n) \leq n!\)
2. Program A is not totally useless as long as \(T(n) \leq 2^n\)
3. Program A is not totally useless as long as \(T(n) \leq n^3\)
4. Program A is not totally useless as long as \(T(n) \leq n^2\)
5. Program A is not totally useless as long as \(T(n) \leq n \log n\)
6. Program A is not totally useless as long as \(T(n) \leq n\)
7. Program A is not totally useless as long as \(T(n) \leq 1\)