What is Big O?

When comparing algorithms, it is typically not sufficient to describe how one algorithm performs for a given set of inputs. We typically want to quantify how much better one algorithm performs when compared to another for a given set of inputs. To describe the cost of a software function (in terms of either time or space), we must first represent that cost using a mathematical function. Let us reconsider finding the ace of spades. How many cards will we have to inspect? If it is the top card in the deck, we only have to inspect 1. If it is the bottom card, we will have to inspect 52. Immediately, we start to see that we must be more precise when defining this function. When analyzing algorithms, there are three primary cases of concern:

• Worst case: This function describes the most comparisons we may have to make given the current algorithm. In our ace of spades example, this is represented by the scenario when the ace of spades was the bottom card in the deck. If we wish to represent this as a function, we may define it as f(n) = n. In other words, if you have 52 cards, the most comparisons you will have to perform will be 52. If you add two jokers and now have 54 cards, you now have to perform at most 54 comparisons.
• Average case: This function describes what we would typically have to do when performing an algorithm many times. For example, imagine your professor asked you to first find the ace of spades, then 2 of spades, then 3 of spades, until you have performed the search for every card in the deck. If you left the card in the deck each round, some cards would be near the top of the deck and others would be near the end. Eventually, each iteration would have a cost function of roughly f(n) = n/2.
• Amortized case: This is a challenging case to explain early in this book. Essentially, it arises whenever you have an expensive set of operations that only occur sometimes. We will encounter this in the resizing of hash tables as well as the prerequisites for Binary Search.

You may wonder why best-case scenarios are not considered. In most algorithms, the best case is typically a small, fixed cost and is therefore not very useful when comparing algorithms.

Asymptotic Analysis

Thus, rather than comparing algorithms based on a speed test or the exact number of operations involved, algorithms are compared using Asymptotic analysis. Asymptotic analysis measures the efficiency of an algorithm, or its implementation as a program, as the input size becomes large. The term “asymptotic” here means basically “the tendency in the long run, as the size of the input is increased.” An asymptotic analysis of an algorithm’s run time looks at the question of how the run time depends on the size of the problem. The analysis is asymptotic because it only considers what happens to the run time as the size of the problem increases without limit; it is not concerned with what happens for problems of small size or, in fact, for problems of any fixed finite size. Only what happens in the long run, as the problem size increases without limit, is important.

There are a few important assumptions and generalizations we’re going to make when using asymptotic analysis.

• When we describe the runtime as a function, the function will be in terms of the size of the input. We will use N to represent the size of the input.
• We’re going to treat all operations as if they cost the same. Technically, multiplication is a more expensive operation than addition, certain memory operations take longer than others, etc. Those differences do not matter in this case.
• We are comparing the growth rate of the algorithms. That is, we are only concerned with how well the algorithm scales as the size of the input increases. Does it take three times more operations or N^2 more operations if we double the size of the input, N? We consider the algorithm that only takes three times more operations as the “more efficient” algorithm.
• We only care about the growth rate after some particular value of N. This is where the “asymptotic” part comes in. Algorithm A is better than Algorithm B as long, after some point, Algorithm A grows more slowly than Algorithm B.
• Growth rates are typically expressed as one of the following functions: [latex]1, logn, n, nlogn, n^x, 2^n[/latex].  These are shown on the graph below.  You can see the relative rate of growth of each function.

Figure by Cmglee under CC BY-SA 4.0

Example: Largest-Value Sequential Search

Consider a simple algorithm to solve the problem of finding the largest value in an array of N integers. The algorithm looks at each integer in turn, saving the position of the largest value seen so far. This algorithm is called the largest-value sequential search and is illustrated by the following function:

// Return position of largest value in integer array A
static int largest(int[] A) {
     int currlarge = 0; // Position of largest element seen
     for (int i=1; i<A.length; i++) { // For each element
        if (A[currlarge] < A[i]) {// if A[i] is larger
            currlarge = i; // remember its position
        }
    }
    return currlarge; // Return largest position
}

Here, the size of the problem is A.length, the number of integers stored in array A. The basic operation is to compare an integer’s value to that of the largest value seen so far. It is reasonable to assume that it takes a fixed amount of time to do one such comparison, regardless of the value of the two integers or their positions in the array.

Because the most important factor affecting running time is normally the size of the input, for a given input size N, we often express the time T to run the algorithm as a function of n, written as T(n). We will always assume T(n) is a non-negative value.

Let us call c the amount of time required to compare two integers in function largest. We do not care right now what the precise value of c might be. Nor are we concerned with the time required to increment variable i because this must be done for each value in the array, or the time for the actual assignment when a larger value is found, or the little bit of extra time taken to initialize currlarge. We just want a reasonable approximation for the time taken to execute the algorithm. The total time to run largest is therefore approximately cN, because we must make N comparisons, with each comparison costing c time. We say that function largest (and by extension, the largest-value sequential search algorithm for any typical implementation) has a running time expressed by the equation

[latex]T(n)=cn[/latex]

This equation describes the growth rate for the running time of the largest-value sequential search algorithm.

Big O Notation

Asymptotic notation gives us a way of describing how the output of a function grows as the inputs become bigger. There are several notations used, but the most important is Big-O. Most often stylized with a capital O, this notation enables us to classify cost functions into various well-known sets. Big-O provides an upper bound for the growth of the runtime. It indicates the upper or highest growth rate that the algorithm can have.

Because the phrase “has an upper bound to its growth rate of f(n)” is long and often used when discussing algorithms, we adopt a special notation, called Big O notation. If the upper bound for an algorithm’s growth rate (for, say, the worst case) is (f(n)), then we would write that this algorithm is “in the set O(f(n)) in the worst case” (or just “in O(f(n)) in the worst case”). For example, if n² grows as fast as T(n) (the running time of our algorithm) for the worst-case input, we would say the algorithm is “in O(n²) in the worst case”.

Formally, we define Big-O as follows:

f(n) = O(g(n)) if f(n) ≤ cg(n) for some c > 0 and all n > n₀.

The constant n₀ is the smallest value of n for which the claim of an upper bound holds true. Usually n₀ is small, such as 1, but does not need to be. You must also be able to pick some constant c, but it is irrelevant what the value for c actually is. In other words, the definition says that for all inputs of the type in question (such as the worst case for all inputs of size n) that are large enough (i.e., n > n0), the algorithm always executes in less than or equal to cf(n) steps for some constant c.

Example

Given T(N) = 64N, we can say T(N) is O(N²) because there is some positive constant c and some value of N for which T(N) ≤ N². The graphs below provide visual proof. Note that the first graph shows 64N > N² when 0 < N < 10. This is allowable. Eventually, there is a value of N where from that point on, N² > 64N (as shown in the second graph).