Evaluating Algorithms

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$