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
• What is a step???

• Our textbook suggests that we should count “constant time operations”

  private static int linearSearch(int[] numbers, int key) {
    for (int i = 0; i < numbers.length; i++) {
       if (numbers[i] == key) {
          return i;
       }
    }
    return -1; // not found
  }

• You try… Count the number of constant time operations for linear search, assuming the worst case (item is not in the array).

• \(W(n) = 3n + 3\)

Alternate Implementation

• How about for this implementation?

  private static int linearSearch1(int[] numbers, int key) {
    int loc = 0;
    for (int val : numbers) {
      if (val == key) {
        return loc;
      }
      loc++;
    }
    return -1; // not found
   }

• \(W(n) = 2n + 2\) (??)

• Does this mean the second implementation is faster?

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) \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\)