Runtime Complexity: Understanding Big-O notation with clear visualizations

If you’re learning to program, or maybe you’re a Computer Science student, you probably heard about runtime complexity, and phrases like “it has a runtime complexity of O(n)“.
Well, before we dive into understanding the subject, lets first make sure we’re all on the same page.

Runtime complexity (also known as time complexity or computational complexity) is a mathematical way that we use in computer science, to describe how many operations are needed in order to run an algorithm or a piece of code.

Why runtime complexity matters

When solving a coding problem you can usually do it in more than one way. Let’s assume you found 2 different coding algorithms that solve your problem, A and B.
When running A on your computer you get the result instantly. When running B on your computer, you have to wait for a minute. Running algorithm B makes the computer work a lot harder (run a lot more operations) to achieve the same final result.
We say that algorithm A has better runtime complexity than algorithm B.

When writing code, you have to be able to analyze the runtime complexity of your solution to be able to tell how efficient it is.

Enter Big-O notation.

Big-O Notation Intuitively

To understand the intuition behind Big-O, let’s look at the following function:

def func(arr):
    results = []

    for first_element in arr:
        for second_element in arr:
            results.append(first_element * second_element)

    for result in results:
        print(2 * result / 3 + 1)

Our function gets an array of size n.
Let’s analyze the number of operations this function performs roughly. We assume multiplication and assignment are one operation.

  • Line 2: 1 assignment operation.
  • Lines 4-6: In each iteration we perform 2 operations (multiplication + append to the results list). We do this in two nested loops over the array. In total 2 \cdot n \cdot n = 2n^2 operations.
  • Lines 8-9: In each iteration we perform 3 operations (multiplication, division and addition). We do this in one loop over our array. In total 3n operations.

In total: 2n^2+3n+1 operations.
However, when we measure our runtime complexity using Big-O, we don’t care about the exact number.

We only care about the most dominant term

When we use Big-O notation, we assume n is extremely large, so we neglect all the terms that are not the most dominant. To prove a point, let’s look at the following table:

n=10n=100n=10000
n^210010,000100,000,000
The larger n grows, the more dominant n^2 becomes when compared to n

The table clearly shows that n^2 is a lot more dominant than n when n is large.
In the case of our previous function, can neglect all the terms that are not n^2. (including the constants)

This leads us to the conclusion:

2n^2+3n+1=O(n^2)

Informally, this means that when n is large, our function is bounded by n^2 when multiplied by a constant. (more on that below)

Before looking at more practical examples, let’s look at the formal mathematical definition of Big-O.
If you only care about the skills needed to analyze your code, you can skip the next section and move to the examples.

Formal Definition

f(n)=O(g(n)) if and only if there exist C > 0, n_0 such that f(n) \le C \cdot g(n) whenever n \ge n_0

Looks scary, doesn’t it? We’ll visualize it soon so it’s easier to understand.
Intuitively, this means we want to find some constant number C to multiply g(n) so it bounds f(n) from a certain point n_0, indefinitely.

To understand the definition, let’s look at our previous example where we said that:
2n^2+3n+1=O(n^2)

In our case:
f(n)=2n^2+3n+1
g(n)=n^2

Our bounding function n^2 does not bound 2n^2+3n+1, but if we choose our constant C=3,
then we have 2n^2+3n+1 \le 3n^2 from the point n_0=3.303 and afterwards.

2n^2+3n+1 \le 3n^2 whenever n_0 \ge 3.303

Note that we only care about what happens when n is very large, so we want to find a point from which the bounding happens, even if it’s very far, and no matter what happens before it.
In our case, this could mean that we could also choose n_0=5 or any point after n_0=3.303.

We can also choose our constant to be C=5 and then any point that is chosen after n_0=1.264 is also okay:

2n^2+3n+1 \le 5n^2 whenever n_0 \ge 1.264

The number of different configurations for the choice of C, n_0 can be infinite. We only need to find one to prove that f(n)=O(g(n)).

Choosing a very big constant doesn’t always work

You may ask yourself, can’t I always choose an extremely large value for C and prove any bounding claim, even if it’s false? The answer is no, and to demonstrate this let’s try to prove the false claim 2n^2=O(n) (spoiler: we’ll fail).
We want to find C>0, n_0 such that 2n^2 \le C \cdot n whenever n \ge n_0.

If we choose C=18 then 2n^2 \le 18n but only while n \le 9.
If we choose C=200 then 2n^2 \le 200n but only while n \le 100.
If we choose C=1000000 then 2n^2 \le 1000000n but only while n \le 500000.

You get the idea. No matter how big of a constant we choose, n^2 grows so much faster than n that from a certain point, it will “outgrow” the initial advantage that is given by the constant.

Most Commonly Used Complexity Functions

complexity functions

This above image shows the most commonly used functions when analyzing complexity. You can clearly see the differences in how quickly n^2 grows when compared to n. See how efficient a logarithmic function is, as it stays relatively flat when compared to the other functions, even when n is large.

When writing our code, we usually want to reach for the solution with the best runtime complexity, if we implemented a O(n) solution but can find a log(n) one, we probably want to do it (unless the implementation makes are code a lot harder to maintain or understand).
If we found a log(n) solution but can find a O(1) (meaning we always perform a constant amount of operations and don’t depend on n at all) solution, even better.

In practice – Code examples

Example 1

def func(arr):
    if len(arr) % 2 == 0:
        print('Even')
    else:
        for element in arr:
            print(element)

This function has 2 branches. The if part and the else part.

  • if part: Constant number of operations (just a print) which we denote by O(1)
  • Else part: we perform a loop over our array with a constant number of operations in each iteration. O(n) \cdot O(1)=O(n).

Note that when analyzing time complexity we usually care about the worst case scenario. (There are cases where we care about the average case, but let’s ignore that for now)
This is why the runtime complexity of our function is: max\{O(1), O(n)\}=O(n).

Example 2

def func(arr_a, arr_b):
    j = 0
    for i in range(len(arr_a)):
        while j < len(arr_b):
            print(i, j)
            j += 1

The function gets 2 arrays, list_a, and list_b of size A,B respectively.
You may be tempted to say this function has a complexity of O(A \cdot B) but don’t be fooled.
Notice that when looping over A, in the first iterations we are also looping over B. From the second iteration, we only perform the “while check” on line 4 because we never reset j=0.

This leaves us with O(B)+(A-1) \cdot O(1)=O(B)+O(A-1)=O(B)+O(A).
We keep both terms because we don’t know the relationship between A and B. If for example you knew that B > A you could say that the function has a runtime complexity of O(B).