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];
  }

• Now you try…

  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
  • Should be an intrinsic step in the algorithm that doesn’t depend on programming language details

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…

Binary Search

   private static int binarySearch(int[] numbers, int key) {
   
      int low = 0;
      int high = numbers.length - 1;
      int mid;
   
      // Loop until "low" passes "high"
      while (high >= low) {

         mid = (high + low) / 2;

         if (numbers[mid] < key) {
            low = mid + 1;
         }
         else if (numbers[mid] > key) {
            high = mid - 1;
         }
         else {
            return mid;
         }
      }
   
      return -1; // not found
   }

Binary Search Analysis

• Informally, we could just try some searches and see show long they take:

• Result:

  $n$	total equality checks
  1	1
  2	2
  4	3
  8	4

• Looks like ${\log }_{2}n+1$

• (For non-powers-of-two $\lfloor {\log }_{2}n\rfloor +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 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)\le n!$
2. Program A is good enough as long as $T(n)\le 2^n$
3. Program A is good enough as long as $T(n)\le n^3$
4. Program A is good enough as long as $T(n)\le n^2$
5. Program A is good enough as long as $T(n)\le n\log n$
6. Program A is good enough as long as $T(n)\le n$
7. Program A is good enough as long as $T(n)\le 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)\le n!$
2. Program A is not totally useless as long as $T(n)\le 2^n$
3. Program A is not totally useless as long as $T(n)\le n^3$
4. Program A is not totally useless as long as $T(n)\le n^2$
5. Program A is not totally useless as long as $T(n)\le n\log n$
6. Program A is not totally useless as long as $T(n)\le n$
7. Program A is not totally useless as long as $T(n)\le 1$