teaching machines

CS 240: Lecture 3 – Measuring Algorithms

August 30, 2021 by . Filed under cs3, fall-2021, lectures.

Dear students:

We talked last week about the arsenal of tools we computer scientists have at our disposal and how each tool has its strengths and weaknesses. To be able to choose which tool to use, we need a way of judging them. Here are a few possible ways we might measure algorithms:

A faster algorithm is a better algorithm. Our choice of data structure will influence an algorithm’s speed. Much of our discussion together will be devoted to measuring the time efficiency of algorithms and data structures. Let’s examine how we measure time efficiency with a case study.

Biggest Difference

Suppose you told by your project manager to write an algorithm to scan a set of numbers and find the biggest, pairwise difference among them. Because your economic model is extremist capitalism, you turn to StackOverflow and find this solution in Ruby:

#!/usr/bin/env ruby

def biggest_difference(numbers)
  max_diff = 0

  for x in numbers
    for y in numbers
      diff = x - y
      if diff > max_diff
        max_diff = diff
      end
    end
  end

  max_diff
end

How does this look to you? Is it correct? Is it simple? Yes on both accounts. It is very space efficient. Apart from the array, it only allocates a couple of extra variables. Is it time efficient? Let’s measure its execution time. We create an array of random numbers and find the biggest difference:

#!/usr/bin/env ruby

require 'benchmark'
require_relative './biggest_difference1.rb'

n = 100

g = Random.new
numbers = Array.new(n) { g.rand(1000000) }
time = Benchmark.measure {
  biggest_difference(numbers)
}
puts time.utime

The execution time seems fine. What if we bump n up? It’s hard to get a sense of how the execution time is changing when doing isolated runs. Instead, let’s make many runs with varying values of n and plot the execution time as a function of n:

#!/usr/bin/env ruby

require 'benchmark'
require_relative './biggest_difference1.rb'

g = Random.new
ns = 30.times.map { |i| i * 100 }

for n in ns
  numbers = Array.new(n) { g.rand(1000000) }
  time = Benchmark.measure {
    diff = biggest_difference(numbers)
  }
  print "(#{n},%.7f)," % time.utime
end

When we paste the output into Desmos and fit the window to the data, we see an interesting shape. As n increases, the execution time increases much faster. This solution is simply not going to scale to large values of n. Perhaps Ruby is the problem. In languages like Java and C++, the high-level code gets compiled down into the “language” of the processor, into very fast machine instructions. This language is really just patterns of electrons. In Ruby, the high-level code is interpreted, which means it never gets turned into fast machine code. Instead, it is evaluated by software, which is slower as it involves a lot of decision making at runtime.

Let’s compare this solution in Java:

public class BiggestDifference {
  public static void main(String[] args) {
    int[] ns = {
       100,  200,  300,  400,  500,  600,  700,  800,  900, 1000,
      1100, 1200, 1300, 1400, 1500, 1600, 1700, 1800, 1900, 2000,
      2100, 2200, 2300, 2400, 2500, 2600, 2700, 2800, 2900, 3000,
    };
    Stopwatch timer = new Stopwatch();

    for (int n : ns) {
      int[] numbers = randomArray(n);
      timer.start();
      biggestDifference(numbers);
      double seconds = timer.stop();
      System.out.printf("(%d,%.6f),", n, seconds);
    }
  }

  private static int[] randomArray(int n) {
    Random g = new Random();
    int[] numbers = new int[n];
    for (int i = 0; i < n; ++i) {
      numbers[i] = g.nextInt(100000);
    }
    return numbers;
  }

  public static int biggestDifference(int[] numbers) {
    int maxDiff = 0;

    for (int x : numbers) {
      for (int y : numbers) {
        int diff = x - y;
        if (diff > maxDiff) {
          maxDiff = diff;
        }
      }
    }

    return maxDiff;
  }
}

The numbers reveal that Java is indeed faster. However, we see the same sort of growth when we plot the execution times. As n increases, the execution time grows faster. If we are dealing with large values of n, even the Java solution will get bogged down. We have reached the point where perhaps we need to rethink the algorithm. Could we implement it in a way that is more time efficient? Yes. Instead of looking at each pair of numbers, we could just find the minimum and the maximum and compute their difference. That would require only one pass through the array instead of a pass per number. Our revised algorithm looks like this in Ruby:

#!/usr/bin/env ruby

def biggest_difference(numbers)
  if numbers.empty? 
    return 0
  end

  min = numbers[0]
  max = numbers[0]

  for number in numbers
    if number < min
      min = number
    elsif number > max
      max = number
    end
  end

  max - min
end

When we plot the times now, we see that the execution time grows at a constant rate. Though the Java solution would be faster, the Ruby solution is plenty fast.

What to Measure

With both the list experiment and the biggest difference experiment, we used execution time to measure the time efficiency. Execution time turns out not to the best measurement for several reasons:

A better measure is the number of steps. A step is loosely defined as a single operation. An algorithm’s number of operations is expressed as a function of n:

$$T(n) = \mathrm{?}$$

Consider this algorithm:

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

How many steps are taken? The += happens n times. So does the array indexing. So does ++i. So does the comparison. We could define T for this algorithm in this way:

$$T(n) = 4n$$

However, this isn’t the code that ultimately gets executed. Rather, the code gets compiled down to a bunch of machine instructions. The array index might expand into five machine instructions. The comparison might expand into three. So, T might more realistically be defined this way:

$$T(n) = 26n$$

While this may be more accurate, the definition of T now depends on the machine again, which will make comparing algorithms on different machines difficult. For this reason, we define T more loosely in terms of some constant coefficient:

$$T(n) = cn$$

All algorithms whose number of steps can be expressed this way are said to have linear time.

How should we define T for this algorithm?

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

The outer loop executes n times. On each iteration, the inner loop executes n times. That gives us this loose definition of T:

$$T(n) = cn^2$$

All algorithms whose number of steps can be expressed this way are said to have quadratic time. Would you rather have a linear time algorithm or a quadratic time algorithm?

Growth Families

Every algorithm we encounter will be judged by its number of operations. In practice, we’ll find that there are just a handful of functions used to describe a function’s time efficiency:

We’ll plot these one at a time in Desmos to see how they compare.

Finding which of these families an algorithm belongs to is a major part of theoretical computer science. Even software developers need to have some sense of them in order to judge the quality and even possibility of their solutions.

Suppose you are trying to crack a numeric password of length n, which means you must test every possible password. What growth family does this algorithm belong to?

We’ll answer this question using peer instruction.

TODO

See you next time.

Sincerely,

P.S. It’s time for a haiku!

Never order food
The menu is way too big
Just say what you want