Algorithm Analysis

Asymptotic analysis in the context of iterative sorts.

  1. Asymptotic Analysis
    1. Model the number of steps
    2. Formalize the runtime model
    3. Asymptotic notation
  2. Iterative Sorts
    1. Sorting definitions
    2. Selection sort
    3. Insertion sort

Asymptotic Analysis

  1. Compare and contrast runtime analysis, asymptotic analysis, and case analysis.
  2. Analyze the order of growth of a function as constant, linear, or quadratic.
  3. Identify big-theta asymptotic notation for the order of growth of a function.

In your previous programming experience, we focused on correctness and maintainability—code that produces the expected output given a particular input, and code that is easy to improve or extend in the future. But, as we’ll see throughout this course, it’s also important that we design programs with a focus on efficiency too.

Experimental runtime analysis is a method for empirically measuring how long a program takes to run by recording exactly how long it takes to run on different inputs. Experimental analysis is particularly helpful for identifying and addressing performance issues by indicating exactly which operations are contributing to high runtime. This data can be used to create graphs that plot the runtime as the input to the program grows larger and larger.

But what if we want to predict the runtime of a program before writing any code? What other methods can we use to help us design the specification to a program so that it meets our performance needs?

Asymptotic runtime analysis is the process of predicting the amount of time an algorithm will take to run on large inputs. Asymptotic analysis focuses on analyzing algorithms, the concepts underlying how programs work. Compared to experimental analysis, which focuses on empirical measurement, asymptotic analysis focuses on reasoning and logic to analyze the runtime of an algorithm.

Computer scientists specifically focus on large inputs (as the size of the input approaches infinity, or its asymptote) rather than small inputs because larger inputs more clearly demonstrate differences in efficiency. For example, the performance issue in ArrayListDeque only appears when a large number of web pages have been stored in browser history; ArrayListDeque is quite fast when only a few web pages have been stored. The differences in runtime become more appreciable when we’re working with a very large number of elements.

The goal of asymptotic runtime analysis is to produce a (1) predictive and (2) easy-to-compare description of the running time of an algorithm. Consider the indexOf method, which returns the index of a target number in an int[] A or -1 if target is not in the array.

static int indexOf(int[] A, int target) {
    for (int i = 0; i < A.length; i += 1) {
        if (A[i] == target) {
            return i;
        }
    }
    return -1;
}

The behavior of the indexOf algorithm depends on the input values.

  1. Initialize an integer index counter, i.
  2. Loop over the length of the array. On each iteration, if the A[i] is the same as the given target, return the current index. Otherwise, increment i.
  3. If no elements in the array are the same as the given target, return -1.

Model the number of steps

How many steps (or operations) are needed to run the algorithm? Operations include assignments, boolean evaluations, arithmetic operations, method calls, etc.

Let’s take a look at these two assignment statements to illustrate how to count steps.

int a = 4 * 6;
int b = 9 * (a - 24) / (8 - 7);
  1. The first assignment to a takes one step (1) to compute 4 * 6 and another step (2) to assign the result to the variable a.
  2. The second assignment to b takes one step (1) to compute a - 24, another step (2) to compute 9 * (a - 24), another step (3) to compute 8 - 7, another step (4) to compute 9 * (a - 24) / (8 - 7), and a final step (5) to assign the result to the variable b.

In total, these two lines of code take 7 steps for the computer to run. The first goal of runtime analysis was to produce a predictive description of the runtime of an algorithm, but in this example, there’s not much to predict: the two assignment statements always take precisely 7 steps.

indexOf is different: it has a loop and an if statement that depends on the values in the A compared to the target. How do we model the number of steps it takes to run an algorithm in general? Here are two factors that can affect the number of steps to compute indexOf.

  1. The length of the A.
  2. The values of each int in the A compared to the value of the target.

The runtime of many algorithms is greatly affected by the size of the input. A small array typically takes little time to run regardless of whether the algorithm is fast or slow. Where we really start to appreciate the differences in runtime is when the array is very large. Therefore, when computer scientists talk about runtime analysis, the default assumption is asymptotic analysis.

Asymptotic analysis is a way of evaluating the efficiency of an algorithm on large inputs. The choice for the “large input” is called the asymptotic variable. For indexOf, the length of the A can be the asymptotic variable.

In this course, we’ll usually tell you the asymptotic variable using the phrases, “with respect to” or “in terms of”. Asymptotic analysis is defined in terms of the asymptotic variable, so make sure to confirm the asymptotic variable before analyzing a program.

But we also know that the runtime depends on other factors such as the relationship between the target and the numbers in the A. Case analysis is a way to account for variation in the model based on interactions between other factors besides the asymptotic variable.

Best case indexOf
The best case (most efficient or fastest) occurs when the target is the same as the A[0]—even when the array is very large.
Worst case indexOf
The worst case (least efficient or slowest) occurs when the target is the same as the last element in the A or not even in the A at all.

All other factors not covered by the asymptotic variable are considered in case analysis. In this course, we’ll focus only on the best and worst case: take all the remaining factors that you have at your disposal and choose a situation that produces the fastest (best case) or the slowest (worst case) runtime.

We now have a predictive model for the number of steps (a proxy for the time) it takes to run an algorithm. But this model is not easy to compare. To communicate our model, we’ll introduce some new vocabulary used to express asymptotic analysis.

Formalize the runtime model

How do we express our model to others so that we can communicate results?

The order of growth relates the size of the input to the time that it takes to run the algorithm on that input. Often, we’ll use a mathematical variable like N to refer to the asymptotic variable.

Best case indexOf orders of growth
In the best case, the order of growth for the runtime of indexOf is constant.
Worst case indexOf orders of growth
In the worst case, the order of growth for the runtime of indexOf is linear with respect to N, the length of A.

When the order of growth is constant, we don’t specify “with respect to N” because constant order of growth implies that the runtime does not scale with N.

Orders of growth help us compare runtime in terms of words like constant, linear, and quadratic. In practice, though, you’ll rarely see computer scientists writing out the full orders of growth sentence. Instead, computer scientists communicate orders of growth using asymptotic notation.

Asymptotic notation

Asymptotic notation provides precise, mathematical shorthand for orders of growth.

Consider this graph that depicts three functions of N.

What do the x-axis and the y-axis represent in the graph?

The x-axis represents the size of the input, N. The y-axis represents the model’s prediction for the number of steps that the algorithm will require for an input of a given size.

The three functions depicted in the graph are:

  1. The top blue function depicts 5N2.
  2. The middle red function depicts 40 sin(N) + 4N2.
  3. The bottom green function depicts 3N2.

The shaded area represents the range between the top and bottom functions.

This graph provides a visual demonstration of the big-theta definition. We can say that the function 40 sin(N) + 4N2 is in Θ(N2) because because it is bounded below by the green function 3N2 (k1 = 3) and bounded above by the blue function 5N2 (k2 = 5).

The red function is only “squeezed” between the blue and green functions for N > 6. This is why big-theta is an asymptotic notation: its logic applies to all values of N greater than some initial N0. When we make a claim about asymptotic runtime, we must make sure that our analysis holds true for all possible “large inputs” N.

Now that we’ve learned the steps to perform asymptotic analysis, we can finally answer the question, “What is the asymptotic runtime of indexOf with respect to N, the length of the input array A?”

Best case indexOf orders of growth
In the best case, the order of growth for the runtime of indexOf is constant.
In other words, in the best case, the asymptotic runtime of indexOf is in Θ(1).
Worst case indexOf orders of growth
In the worst case, the order of growth for the runtime of indexOf is linear with respect to N, the length of A.
In other words, in the worst case, the asymptotic runtime of indexOf is in Θ(N) with respect to N, the length of A.

Iterative Sorts

Insertion.javaSelection.java

  1. Describe the problem of sorting, ordering relations, and stability.
  2. Trace each iteration of selection sort and insertion sort.
  3. Identify a run of selection sort and insertion sort on an array.

There are different ways to find duplicates in an array. dup1 represents one way to solve the problem: exhaustively check all possible pairs of elements and return whether a duplicate exists among them. In the worst case, dup1 required quadratic time to return an answer.

How long might a quadratic time algorithm need to run?

  • When N = 10, less than 1 second.
  • When N = 100, less than 1 second.
  • When N = 1,000, about 1 second.
  • When N = 10,000, about 2 minutes.
  • When N = 100,000, about 3 hours.
  • When N = 1,000,000, about 12 days.
How long might a linear time algorithm need to run?
  • When N = 10, less than 1 second.
  • When N = 100, less than 1 second.
  • When N = 1,000, less than 1 second.
  • When N = 10,000, less than 1 second.
  • When N = 100,000, less than 1 second.
  • When N = 1,000,000, about 1 second.

What can we learn from these findings?

Many algorithms (including all algorithms in this course) are fast on tiny inputs when N < 1000
While there may be situations where we care about the efficiency of algorithms processing tiny inputs, these differences are often unnoticeable. When they are noticeable, they may be caused by unanticipated changes in your computer’s workload.
Differences become more appreciable when inefficient algorithms run on inputs of size N > 1000
Whether the runtime is tolerable depends on the problem. An inefficient algorithm may be acceptable if we only need to run it infrequently, the size of the input is not particularly big, or the amount of processing power can make up for the time.
Therefore, efficient algorithms are often needed to process even moderately-large data frequently.

However, if our array is sorted, then returning whether there are duplicates in the array takes much less time in the worst case. In a sorted array, all duplicate elements must be stored right beside each other. It turns out that a significant number of problems in computer science get a lot easier and a lot more efficient to solve if we can first sort our data. Without sorting, many of the systems and software that we have today would not be possible purely because things (like duplicate finding) would take far too long to run.

But data doesn’t always come to us in a pre-sorted form. How do we sort—rearrange into order—an array of elements?

Sorting definitions

Sorting is the problem of rearranging a sequence of elements into non-decreasing order. How do we define the order of elements? For numbers, smaller values appear before larger values in non-decreasing order. But sorting objects are a bit more complicated.

For objects, the implementer of the class is responsible for defining the ordering relation. Just as numbers have a natural definition for less-than, equal-to, and greater-than relationships, the class’s compareTo method provides a way to specify the relative order of any two elements of that class. For example, if we have emails where each Email object has a date, sender, and text, the compareTo method could be defined like an inbox where emails are sorted only by date.

public int compareTo(Email other) {
    // Compare the date of this email to the date of the other email.
    return this.date.compareTo(other.date);
}

In other situations like searching for all the emails from a particular sender (ignoring date), it might be more helpful to sort by the sender primarily and the text of their message secondarily.

public int compareTo(Email other) {
    // Compare the sender of this email to the sender of the other email.
    int cmp = this.sender.compareTo(other.sender);
    if (cmp != 0) {
        // If the senders are different, return the difference.
        return cmp;
    }
    // Otherwise, the senders are the same, so compare by text content.
    return this.text.compareTo(other.text);
}
In the email example, where is the compareTo method defined?

The compareTo method for the Email class is defined inside the Email class by the people who wrote the class. When we talk about sorting algorithms, the author of the sorting algorithm has no idea the exact objects that they’re sorting or the ordering relation. A sorting algorithm just calls compareTo to determine whether an object should appear before or after another object. Sorting involves repeatedly asking, “Is this object less-than, equal-to, or greater-than this other object?” by repeatedly calling the compareTo method.

A sort is stable if it preserves the original order of equivalent keys. Stability can affect the final sorting output when there are two or more elements considered equal according to the ordering relation. For basic data types like numbers, stability doesn’t matter: any two numbers that share the same numeric value are just the same either way. But for objects like emails, stability can make a big difference. Imagine sorting emails by sender name: you’ll often receive many emails from the same sender, so a stable sort for emails will sort by sender name and, for each sender name, maintain the original order of emails that you received from that sender. An unstable sort doesn’t guarantee the original order of emails for each person.

So how do we sort an array? In this lesson, we’ll introduce two iterative sorting algorithms: selection sort and insertion sort.

Selection sort

In each iteration, selection sort selects the smallest unsorted element and swaps it into its sorted place.

Selection sort has an important invariant that was introduced called iterative improvement. We keep track of a sorted elements portion at the front of the array and gradually grow the number of sorted elements. Once the sorted elements portion reaches the full length of the array, we’re done sorting the array!

Give an asymptotic runtime analysis of selection sort with respect to the number of elements.

First, consider if there are any other factors besides number of elements (the asymptotic variable) that could require further case analysis. In selection sort, there are no other factors that affect the runtime because we always need to scan across the entire unsorted elements portion of the array to find the smallest unsorted element.

The runtime for selection sort is similar to the runtime for dup1, which we described using the summation (N - 1) + (N - 2) + … + 3 + 2 + 1, which we determined to have a quadratic order of growth. In other words, we can say that selection sort is in Θ(N2).

Insertion sort

In each iteration, insertion sort inserts the next unsorted element into the sorted elements portion at the front of the array by swapping it left one index at a time until it is in its correct position. Like selection sort, insertion sort is also an iterative improvement sorting algorithm.

Give an asymptotic runtime analysis of insertion sort with respect to the number of elements.

Unlike selection sort, insertion sort is affected by the order of elements. When the input is already sorted, insertion sort has a linear order of growth because there are no elements that need to be swapped to the left. On the other hand, given a reverse-sorted input, insertion sort needs to perform a very large number of swaps to move each next unsorted element into its correct position. The summation is exactly the same as dup1 and selection sort, which we determined to have a quadratic order of growth.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose either SEL or INS from the top navigation bar to switch to selection sort or insertion sort respectively. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization