Algorithm Analysis Fundamentals

Introduction

The overall goal of this chapter is to deal with a seemingly simple question: Given an algorithm, how good is it? I say "seemingly" simple because unless we define what we mean by "good", we cannot answer the question. Do we mean how elegant it is? How easy it is to understand? How easy it is to update if/when necessary? Whether or not it can be generalized?

Although all of these may be important questions, in algorithm analysis we are usually more interested in the following two questions: How long does the algorithm take to run, and how much space (memory) does the algorithm require. In fact, we follow the tradition of most books and focus most of our discussion on running time. This is usually reasonable since the amount of memory used by most algorithms is not large enough to matter. There are times, however, when analyzing the space required by an algorithm is important. For instance, when the data is really large (e.g. the graph that represents friendships on Facebook) or when you are implementing a space-time-tradeoff algorithm.

This page introduces the basic ideas used in algorithm analysis: why raw running times can be misleading, how input size affects running time, how best-case, worst-case, and average-case analysis differ, and how to recognize common time complexities.

Why Asymptotic Analysis?

Since this page focuses mostly on running time, our next task is to decide what "running time" should mean. At first, it might seem enough to time a program with a stopwatch, but that measurement depends on the computer, the programming language, the compiler, the operating system, and even what else the machine is doing. To compare algorithms rather than particular program runs, we need a more stable way to measure time.

So what should we count? There are several reasonable possibilities:

• Wall-clock time: The actual elapsed time from when the program starts to when it finishes. This is what a stopwatch would measure.
• CPU time: The amount of processor time spent running the program. This may differ from wall-clock time because the computer may also be running other programs or using multiple processors.
• Number of operations: The number of basic steps the algorithm performs, such as comparisons, assignments, arithmetic operations, or array accesses.

Because the running time of an algorithm is greatly affected by the characteristics of the computer system (e.g. processor speed, number of processors, amount of memory, file-system type, etc.), the running time does not necessarily provide a comparable measure, regardless of whether you use CPU time or wall-clock time. The next question asks you to think about why.

The answer to the previous question should make it clear that you cannot compare the running times of algorithms if they were run on different machines. Even if two algorithms are run on the same computer, the wall-clock times may not be comparable.

In fact, if you run the same algorithm on the same machine multiple times, it will not always take the same amount of time. Sometimes the differences between trial runs can be significant.

So the CPU-time turns out to be a pretty good measure of algorithm performance. Unfortunately, it does not really allow one to compare two algorithms. It only allows us to compare specific implementations of the algorithms. It also requires us to implement the algorithm in an actual programming language before we even know how good the algorithm is (that is, before we know if we should even spend the time to implement it).

But we can analyze and compare algorithms before they are implemented if we use the number of instructions as our measure of performance. There is still a problem with this measure. What is meant by an "instruction"? When you write a program in a language such as Java or C++, it is not executed exactly as you wrote it. It is compiled into some sort of machine language. The process of compiling does not generally involve a one-to-one mapping of instructions, so counting Java instructions versus C++ instructions wouldn't necessarily be fair. On the other hand, we certainly do not want to look at the machine code in order to count instructions—machine code is ugly. Further, when analyzing an algorithm, should we even take into account the exact implementation in a particular language, or should we analyze the algorithm apart from implementation?

O.K., that's enough of the complications. Let's get to the bottom line. When analyzing algorithms, we generally want to ignore what sort of machine it will run on and what language it will be implemented in. We also generally do not want to know exactly how many instructions it will take. Instead, we want to know the rate of growth of the number of instructions. This is sometimes called the asymptotic running time of an algorithm. In other words, as the size of the input increases, how does that affect the number of instructions executed? We will typically use Asymptotic Notation to specify the running time of an algorithm. We will call this the time complexity (or often just complexity) of the algorithm.

Analyzing Algorithms

Algorithm analysis involves determining the size of the input, \(n\), and then finding a function based on \(n\) that tells us how long the algorithm will take if the input is of size \(n\). By "how long" we of course mean how many operations.

The examples in this section use algorithms that should be familiar from an earlier programming or data structures course. The goal is not to introduce new algorithms, but to practice analyzing simple ones carefully.

We will start by deciding what counts as the input size, then look at how to count operations, how best-case, worst-case, and average-case analysis differ, how to choose which operation to count, and how to analyze simple loops.

    int sequentialSearch(int a[], int n, int val) {
        for(int i=0; i<n; i++) {
            if(a[i]==val) {
                return i;
            }
        }
        return -1;
    }

    int sequentialSearch(int a[], int n, int val) {
        for(int i = 0; i < n; i++) {
            if(a[i] == val) {
                return i;
            }
        }
        return -1;
    }

    int total = 0;
    for (int i = 0; i < n; i++) {
        total = total + a[i];
    }

    int sumArray(int a[], int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = sum + a[i];
        }
        return sum;
    }

    int max(int x, int y) {
        if (x >= y) {
            return x;
        } else {
            return y;
        }
    }

    int maximum(int a[], int n) {
        int currentMax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            currentMax = max(currentMax, a[i]);
        }
        return currentMax;
    }

    int total = 0;
    for (int i = 0; i < n; i++) {
        total = total + list.get(i);
    }

    boolean isSorted(int a[], int n) {
        for (int i = 0; i < n - 1; i++) {
            if (a[i] > a[i + 1]) {
                return false;
            }
        }
        return true;
    }

    int q = 0;

    for (int i = 1; i <= n; i++) { 
        q = q + i * i;
    }

    for (int j = 1; j <= n; j++) {
        q = q * j;
    }

    double v = 0;

    for (int i = 1; i <= n; i++) { 
        for (int j = 1; j <= n; j++) { 
            v = v + A[i] * A[j];
        }
    }

for(stair 1 through 10)
    climb stair
for(stair 1 through 10)
    climb stair

for(floors 1 through 10)
    for(stair 1 through 10)
        climb stair

    int k = 50;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            a[i][j] = b[i][j] * x;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n * n; j++) {
            a[i][j] = b[i][j] * x;
        }
    }

Common Time Complexities

Once we analyze an algorithm, the final answer often matches one of a small number of common growth rates. The table below lists several common complexity classes in increasing order of growth of the function \(f(n)\). Since \(f(n)\) represents running time, larger growth rates generally describe algorithms that scale worse as \(n\) increases.

These names are useful shortcuts, but they are not substitutes for analysis. A loop does not automatically imply linear time, and nested loops do not automatically imply quadratic time. The bound depends on how many times the relevant operations execute.

Let's see an example of an algorithm with each of the given complexities.

    int theFifthElement(int a[], int n) {
        return a[4];
    }

    int sumArray(int a[], int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = sum + a[i];
        }
        return sum;
    }

    int[][] pairSums(int a[], int n) {
        int sums[][] = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sums[i][j] = a[i] + a[j];
            }
        }

        return sums;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            C[i][j] = 0;
            for (int k = 0; k < n; k++) {
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }

Later we will see an algorithm for matrix multiplication with a more interesting complexity. It is called Strassen's Algorithm and it has a complexity of about \(\Theta(n^{2.8})\) (to be precise, its complexity is \(\Theta(n^{\log_2 7})\)).

Generally speaking, we consider algorithms whose complexity is no worse than polynomial to be efficient. This does not mean that every polynomial-time algorithm is practical. For example, an algorithm with complexity \(\Theta(n^{100})\) would be polynomial, but it would be useless for all but very small inputs. Still, polynomial time is an important dividing line because, for a fixed exponent, the running time grows much more slowly than exponential functions such as \(2^n\).

Exponential-time algorithms are usually considered impractical, especially when \(n\) can be even moderately large. There are exceptions, however. Sometimes the problem itself requires exponential work. For example, an algorithm that lists all subsets of an \(n\)-element set must take at least \(\Theta(2^n)\) time because there are \(2^n\) subsets to output. In that case, the exponential running time is caused by the size of the required output, not by a poor algorithm design.

Summary

Algorithm analysis describes how the work done by an algorithm grows as the input size grows. We usually do this by choosing representative operations, counting how often they execute, and simplifying the result using asymptotic notation.

Remember that a faster-growing complexity function describes a slower-scaling algorithm. For example, \(n^2\) grows faster than \(n\), so a \(\Theta(n^2)\) algorithm generally scales worse than a \(\Theta(n)\) algorithm.

The examples on this page used relatively simple loops and familiar operations. On the Algorithm Analysis Examples page, we will apply the same ideas to algorithms where the loop bounds, helper methods, or data structures make the analysis less direct.

Reading Comprehension Questions

1. Measuring Running Time: Why do we usually avoid using wall-clock time as the main way to compare algorithms?
2. Input Size: For an algorithm that takes an array of \(n\) values and one extra number \(val\), why do we usually say the input size is \(n\), not \(n+1\)?
3. Representative Operation: In sequential search, why is the comparison a[i] == val a reasonable operation to count?
4. Best Case: Why is the best-case complexity of sequential search \(\Theta(1)\) even when the input array has size \(n\)?
5. Average Case: Why is average-case analysis usually more difficult than worst-case analysis?
6. Method Calls: Why is it dangerous to assume that a method call inside a loop takes constant time?
7. Nested Loops: Explain why nested loops do not automatically imply \(\Theta(n^2)\) running time.
8. Growth Rates and Algorithms: If \(n^2\) grows faster than \(n\), why do we say a \(\Theta(n)\) algorithm scales better than a \(\Theta(n^2)\) algorithm?

In-Class Activities

1. Timing Is Not Enough: Suppose two students implement algorithms for the same problem. One program takes \(12\) seconds on a laptop, and the other takes \(4\) seconds on a lab computer. In small groups, list at least four reasons why this does not prove that the second algorithm is better. Then decide what information would make the comparison more meaningful.
2. Choose the Input Size: For each situation below, identify a reasonable input-size variable or variables. Briefly justify your choices.
   1. An algorithm processes an array of \(n\) integers and a target value.
   2. An algorithm processes an \(r\) by \(c\) image.
   3. An algorithm processes a graph with \(V\) vertices and \(E\) edges.
   4. An algorithm processes two arrays, one of size \(n\) and one of size \(m\).
3. What Should We Count? Consider the following code.
   

   int countPositive(int a[], int n) {
       int count = 0;
       for (int i = 0; i < n; i++) {
           if (a[i] > 0) {
               count++;
           }
       }
       return count;
   }

   
   Identify two reasonable operations to count. For each choice, decide whether it captures the growth rate of the whole algorithm.
4. Best, Worst, and Average Inputs: For sequential search on an array of size \(8\), write down one input/search-value pair that gives the best case and one that gives the worst case. Then describe what assumptions would be needed before computing an average case.
5. Same Code Shape, Different Costs: The following loop looks simple.
   

   int total = 0;
   for (int i = 0; i < n; i++) {
       total = total + list.get(i);
   }

   
   Analyze it twice: first assuming list.get(i) takes \(\Theta(1)\) time, and then assuming list.get(i) takes \(\Theta(i)\) time. Explain why the answers differ even though the loop structure did not change.
6. Loop Bounds Matter: Each of the following fragments contains nested or repeated loops. For each one, count how many times x++ executes and give the complexity. Be careful: the answer is not determined just by the number of loops.

   1. for (int i = 0; i < n; i++) {
          for (int j = 0; j < 20; j++) {
              x++;
          }
      }

   2. for (int i = 0; i < 20; i++) {
          for (int j = 0; j < n; j++) {
              x++;
          }
      }

   3. for (int i = 0; i < n; i++) {
          x++;
      }
      for (int j = 0; j < n * n; j++) {
          x++;
      }

   4. for (int row = 0; row < r; row++) {
          for (int col = 0; col < c; col++) {
              x++;
          }
      }

7. Classify the Complexity: Match each expression with its common name: constant, logarithmic, linear, linearithmic, quadratic, polynomial, or exponential. \[ \Theta(1),\quad \Theta(n^2),\quad \Theta(2^n),\quad \Theta(n\log n),\quad \Theta(\log n),\quad \Theta(n),\quad \Theta(n^5) \] Then rank the expressions in increasing order of growth.
8. Faster-Growing Versus Faster Algorithm: Work with a partner to explain the following statement in your own words: "A faster-growing complexity function describes a slower-scaling algorithm." Use \(\Theta(n)\) and \(\Theta(n^2)\) as your example, and include a short numerical comparison using \(n=10\), \(n=100\), and \(n=1000\).

Homework Problems

1. Choosing Input Size: For each algorithm description below, identify a reasonable input-size variable or variables. Briefly justify your answer.
   1. An algorithm checks whether a word of length \(n\) is a palindrome.
   2. An algorithm multiplies two \(n\) by \(n\) matrices.
   3. An algorithm determines whether a graph with \(V\) vertices and \(E\) edges is connected.
   4. An algorithm compares every value in an array of size \(n\) with every value in an array of size \(m\).
2. Representative Operation: Consider the following algorithm.

   int countOccurrences(int a[], int n, int val) {
       int count = 0;
   
       for (int i = 0; i < n; i++) {
           if (a[i] == val) {
               count++;
           }
       }
   
       return count;
   }

   1. Choose a representative operation to count.
   2. How many times does that operation execute?
   3. Give the best-case, worst-case, and average-case complexities.
   4. Explain why this differs from sequential search, even though both compare array entries to val.
3. Best Case Is Not Smallest Input: Consider the following algorithm.

   boolean containsNegative(int a[], int n) {
       for (int i = 0; i < n; i++) {
           if (a[i] < 0) {
               return true;
           }
       }
   
       return false;
   }

   1. Describe an input of size \(n\) that results in the best case complexity.
   2. Describe an input of size \(n\) that results in the worst case complexity.
   3. Give the best-case and worst-case complexities.
   4. Explain why the best case is not found by setting \(n=0\).
4. Hidden Cost of a Method Call: Suppose bag.contains(x) takes \(\Theta(1)\) time in one implementation and \(\Theta(n)\) time in another implementation, where \(n\) is the number of items in bag. Analyze the following code under both assumptions.

   int countMatches(int a[], int m, Bag bag) {
       int count = 0;
   
       for (int i = 0; i < m; i++) {
           if (bag.contains(a[i])) {
               count++;
           }
       }
   
       return count;
   }

   1. Give the complexity if bag.contains(x) takes \(\Theta(1)\) time.
   2. Give the complexity if bag.contains(x) takes \(\Theta(n)\) time.
   3. Explain why the answer should use both \(m\) and \(n\) in the second case.
5. Loop Bounds: For each code fragment below, count how many times x++ executes and give the tight asymptotic complexity.

   1. for (int i = 0; i < n; i++) {
          x++;
      }
      
      for (int j = 0; j < n * n; j++) {
          x++;
      }

   2. for (int i = 0; i < n; i++) {
          for (int j = 0; j < 5; j++) {
              x++;
          }
      }

   3. for (int row = 0; row < r; row++) {
          for (int col = 0; col < c; col++) {
              x++;
          }
      }

   4. for (int i = 0; i < n * n; i++) {
          for (int j = 0; j < 3; j++) {
              x++;
          }
      }

6. Rank the Algorithms: Suppose several algorithms solve the same problem and have the following worst-case complexities: \[ \Theta(n),\quad \Theta(n^2),\quad \Theta(\log n),\quad \Theta(2^n),\quad \Theta(n\log n),\quad \Theta(1). \]
   1. Rank them from best-scaling to worst-scaling.
   2. Which of these would usually be considered efficient?
   3. Explain why "best-scaling" does not always mean "fastest on every input."
7. Output Size and Exponential Time: An algorithm prints every binary string of length \(n\).
   1. How many binary strings of length \(n\) are there?
   2. Why must any algorithm that prints all of them take at least exponential time?
   3. Explain why this exponential running time is not necessarily evidence of a poor algorithm.