Computer Science for STEM: The PreTeXt Interactive Edition

A common question that comes up when programming is: "How long will my program take to run?". Even if a program provides the correct output, if it takes too long to finish then it is unacceptable. There is a problem here though, it’s impossible to reliably say exactly how long a program will take to run. It depends on too many things. The capabilities of the computer running the code, what else is running on the computer, and the size of the input are just some of the things that would need to be considered.

To simplify this issue, we’ll give up trying to estimate exactly how long a program will run, and instead look at the biggest factor that affects existing code: the size of the input. If we wrote a program that ran for 60 seconds on 100 megabytes of input data, how should we expect the program to react to 200 megabytes of input data? Maybe it would run in 120 seconds (twice the data for twice the run time)? Maybe it would still run in 60 seconds, assuming that extra data isn’t used. Or maybe the program would run for far longer. The issue is that we don’t know what the relationship is between the size of the input data and the behavior of the program.

This is where Big O Analysis comes in. Big O is a notation computer scientists use to describe the relationship between the size of the input data and the behavior of the program. These terms are written like a mathematical function using the variable n. n as a variable represents the size of the input data provided to the program. The Big O function tells us how n affects the time the program will take to complete.

Consider the example we had before. We have a program that takes 60 seconds to run on 100 megabytes of input data, we’d like to know (roughly) how long the program might take to run on 200 megabytes of input data. If we know the run time of the program is the function f(n) = n^2, with n being the size of the data, now we have enough information to make a guess. If n is doubled, then the time the program runs for will quadruple! (2*n)^2 = 4 * n^2.

The formal mathematical notation for Big O is denoted with a capital O (a big o!) followed by parentheses. Inside of the O() is most commonly some term of n. In our previous example, we would say the program has O(n^2) behavior.

Different functions of n have different magnitudes, which helps us to quantify how quick or slow an algorithm is relative to the input size n. From left to right, left being the quickest time and right being the slowest time, we typically see these complexities:

O(1), O(logn), O(n), O(nlogn), O(n^2), O(n^3), O(2^n), O(n!).

Big O is like a limit in that only the most significant terms matter as n gets bigger and bigger. We typically expect n to be very, VERY large because small inputs aren’t as strongly affected by time limits. If a program takes 0.001 seconds to run with most normal data, is it really a big deal if it takes 0.004 seconds on occasion? What if we were dealing with a program that had to run for a month though? Now that factor of four starts to hurt a lot more.

There is another important aspect that we have ignored up to this point: programs can often have wildly different behavior depending on their input. Consider a contrived example:

var = input()
if 'a' in var:
	while True:
		print("run forever!")
else:
	print("done")

In this program, the size of the input doesn’t matter as much as whether the input string contains a letter "a" or not. If it does, the program runs forever. If it doesn’t, the program ends almost immediately. How do we reconcile this with our Big O notation? The answer is to be a pessimist. We adopt the assumption that everything that can happen to slow down our program will happen. In the code above, we assume that the input ALWAYS will contain an "a". This assumption is broadly known as the "worst case". Big O notation uses this assumption by default in every instance you will see it (at least in this class). Any other case besides "worst" will be labeled.

Let’s look at some more examples:

sum = 1 + 1
print(sum)

This code has a Big O of O(1), also referred to as constant time. This is because the program does nothing with its input. In fact, it doesn’t even take input! Constant time operations are typically things in code which do not loop. A constant time program suggests it will always finish in a consistent amount of time, no matter what happens.

Now, let’s check out an example with a loop:

def example_func(n):
    for i in range(n):
        print(i)

As you can see, this function simply prints 0 to n. Each print takes a little time, so a larger n means a longer program run time. We denote the complexity of example_func as O(n), because whether n = 100 or n = 10000000, as the complexity trends to infinity, it remains O(n).

In the last code example, O(n) was the complexity for all cases, because the loop always goes to n.

This figure shows complexities as a graph and which ones are considered "desirable" or at least "acceptable". Context mostly determines if these are "good" terms or not, but do strive to never write something worse than O(n^3)!

It may be difficult to appreciate the implications of these terms when first seeing them. Let’s say we have a set of algorithms with the following complexities, but they all run with the same time (1 milliseconds) for n = 10. This table shows what will happen if we increase the size of the input:

As you can see, what started off as a negligible difference exploded into a totally unacceptable time for larger input sizes applied to larger Big O terms. Examples like these are precisely why computer scientists are so fixated on Big O. 100000 data points is not a lot of data. Large tech companies are often running code on billions or trillions of data points, and anything less the most efficient code won’t be able to run at-scale.

We will end this section with a disclaimer. We have only covered the bare basic concepts of Big O here today. If you continue to study computer science, you’ll have more opportunities to explore it in much more detail, including seeing the formal definition of Big O as well as learning how to determine the Big O of your own code. For this specific class, we only ask you to be familiar with the notation of Big O and have a basic intuition behind what it communicates.