Programming Basics

Time Complexity of Algorithms— Big O Notation Explained In Plain English

What’s O(1)?

“When can you get me back last month’s sales report?” Billy asked. “In two days.” John said. “Can’t it be sooner?” “No, sir. It’s not about me — it’s the computer. It just needs time to process the data and run the analyses.”

It’s not an untypical conversation that can happen in any company. The information that John was trying to convey is clear. The time-limiting factor in his generating the report is the computer — more precisely, it’s the program or the pertinent algorithms used in the program.

What’s an algorithm?

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. — Wikipedia

With this definition, we can understand that an algorithm is essentially specific mathematical operations that process some input data and output desired values. To help you understand what an algorithm is, let’s consider a trivial example below.

It’s Python code for conceptual purposes, and the algorithm can be easily implemented in any programming language. For clarity, all the code is explained with comments (those starting with the # sign) and the variables are named in a way for good readability.

The above function can be considered a simple algorithm, which calculates the total daily sales by processing the sale records. One particular thing to note is that the code in lines 6 and 7 is an iteration loop, which goes over each of the sale records and adds it to the running total.

Time Complexity and O(n)

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. — Wikipedia

The definition is very straightforward and we can understand that time complexity simply refers to the time needed to run a certain algorithm.

Following the same example in the above section, imagine that the number of sale records is 100 and then the iteration loop will run the addition 100 times.

How about 1000 records? We need to run the addition for 1000 times.

How about 10000 records? We need to run the addition for 10000 times.

…and so on

With the assumption that each additional costs the same amount of time, as you can tell, the time of running the algorithm depends on the number of sale records. More specifically, such dependence is a positive linear relationship — the more records, the more time.

Mathematically, the relationship can be described using the following equation. In essence, the total time is proportionate to the number of records at the rate as defined by the coefficient.

total_time = coefficient * record_number

To check if it’s the case, we can do some experiments by running the algorithm with different numbers of sale records, ranging from 1 to 100,000,000. The results are shown below.

The left panel shows you the numeric results regarding the experiment. As you can see, the higher number of sales records, the longer time the function needs to calculate the total sales amount.

To show the result in the figure, we can calculate the logarithmic values of these measures, and the converted numbers are plotted in the right panel. Clearly, it’s a linear relationship between the number of sales records and the time needed.

But how can we denote the time complexity of this algorithm?

It comes to the Big O Notation, which is defined below.

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. — Wikipedia.

Using the Big O Notation, the time complexity for the algorithm discussed above can be expressed as O(n), which simply means that the time complexity to calculate the total sale amount is linearly dependent on the number of sale records. More generally, the number or expression in the parentheses denotes the complexity of the algorithm.

What’s O(1)?

This notation means that no matter the input size (n), the algorithm uses a fixed amount of time to output the desired value. In other words, we refer to the specific kinds of algorithm constant time O(1) algorithm.

In programming, a common O(1) algorithm has to do with hashing. At its core, hashing is the process of converting input values to unique output values. There are several potential benefits of hashing, such as masking the original values and ensuring the uniqueness of elements in a container data type.

For example, in Python, the dict is a collection data type that consists of key-value pairs. It requires that its keys need to be all hashable, which allows the look-up time to be constant. In other words, it doesn’t take any longer to get a key’s value if there are 1 million elements than 100 elements in the dict object.

Here’s some simple code that allows us to test if this is the case.

# Import the random module for some specific random functionality
import random

# Import the timeit module to calculate the operation time
import timeit

# Define a function that creates needed dict and item to fetch
# We'll change the n to create dict of different sizes
def dict_look_up_time(n):
    # Random numbers with length of n
    numbers = list(range(n))
    random.shuffle(numbers)

    # Create the dict
    d0 = {x: str(x) for x in numbers}
    
    # Create the random key
    random_int = random.randint(0, n-1)
    
    # Calculate the needed look up time
    t0 = timeit.timeit(lambda: d0[random_int], number=10000)

    return t0

As shown in the above code, we create a function generate_number_dict that can create a dict object that has a particular number (n) of elements and a random integer. To evaluate the time needed, we can do the following computations. As you can tell, the times are all about at the same level, suggesting the O(1) time complexity.

>>> # n=10, 100, 1000, 10000, 100000, 1000000, 10000000
>>> dict_look_up_time(10)
0.0011370450083632022
>>> dict_look_up_time(100)
0.0011604460014495999
>>> dict_look_up_time(1000)
0.0012731300084851682
>>> dict_look_up_time(10000)
0.0012891280057374388
>>> dict_look_up_time(100000)
0.0012689560098806396
>>> dict_look_up_time(1000000)
0.0015105670026969165
>>> dict_look_up_time(10000000)
0.0015161900082603097

General Discussion

In the above sections, we have learned what time complexity means and how we can use the Big O notation to denote time complexity. More specifically, we studied two realistic examples about O(n) and O(1). As shown in the figure below, the green line shows the O(n) time complexity and the purple line show the O(1) time complexity.

The figure also shows you other kinds of time complexity, such as O(n*n) and O(sqrt(n)). As you can tell, the steeper the slopes are, the higher the time complexity they have. For example, O(1) complexity has a slope coefficient of 0, while O(n) has a slope coefficient of 1 (or some other fixed number in reality). When the time complexity is n! (3! = 3 * 2 * 1, 4! = 4 * 3 * 2 * 1), the time needed for an input size of 100 or 200 is already enormous!

One outstanding question is how to analyze the time complexity. Well, one simple working solution is that you can test your algorithm with a smaller dataset. If it’s OK time-wise, gradually add more data and see if any performance worsens.

However, this approach works practically, but in reality, you can always have some abstract analysis of your code. In essence, you can simply estimate the number of basic steps that your algorithm needs to run to generate the ideal output.

Take the algorithm that calculates the total sale amount, you know that if we have X number of records, we need to run the addition for X times. In other words, the algorithm needs X steps to produce the output with input data of size X. In this case, we can presume that the algorithm has a time complexity of O(n).

Consider the following hypothetical example. In the code below, we have a nested loop (an iteration loop nested in another loop). As you can estimate, the total number of iterations will be equal to n * n. For example, if n=4, we’ll have to run the addition for 16 times. If n=5, the number of additions will be 25.

With these simple calculations, do you know what the time complexity of this algorithm is?

def another_algorithm(n):
    running_total = 0
    for number_i in n:
        for number_j in n:
            running_total += number_i + number_j
    return running_total

Yes, I guess you got the right answer — the time complexity is O(n*n). It’s not that hard, right?

The present article uses some simplified examples, but in reality, the analysis of complex algorithms can be a lot harder. Nevertheless, the purpose of the current piece is just to provide a 30,000 feet view of the time complexity of algorithms. I hope that you’ve learned how to use the Big O notation to indicate an algorithm’s time complexity by conducting a very basic analysis.

The key takeaway is that if it’s all possible, you always want to minimize the time complexity of your algorithms.

To learn more about time complexity and Big O notation, here’s an excellent reference that you can take a look at.