Data Structures and Algorithms — Asymptotic Notation

When we analyze algorithms, the rate of growth of the algorithm is of most interest. Rate of growth will allow us to understand how the number of operations an algorithm requires changes based on the input, which gives us the best idea of an algorithm’s overall performance. This idea comes from a mathematical concept known as asymptotic notation. This notation allows us to discuss how a function grows as its input gets very large (in other words, as n approaches infinity, what does f(n) do?).

To formalize this idea, we need to first explore algorithms with runtimes varying based on their input. Consider our linear search algorithm:

def linearSearch(list, x):
found = False
i = 0

while not found and i < len(list):
    if list[i] == x:
        found = True
    else:
        i += 1

if not found:
    i = -1
return i

When you analyze this algorithm, you will notice something interesting about the while loop. It terminates at different times depending on the input that is provided to the function. Take for example the following case:

l = [1,2,3,4,5]
linearSearch(l,1)

In this example, our while loop only runs 1 time. Contrast this with the following input:

l = [1,2,3,4,5]
linearSearch(l,6)

In this example, the loop runs 5 times. We can see that our runtime varies not just based on input size, but also based on the input itself. How do we account for this?

The answer is to divide inputs into three main cases:

• The best case
• The average case
• The worst case

We can then analyze each case and generally conclude how long it takes to run for each case. For the most part, we will care only about the worst case. This is because the worst case guarantees the runtime of our algorithm. As an example, consider what the worst case of linear search is. This case would occur when we need to search the entire list for the value we want. In this case, our while loop runs n times, where n is the size of the list. Now technically, our loop contains many constant time operations, but we only care about how runtime grows based on the input size. Keeping this in mind, we can simplify the many operations in the loop to a single operation. After doing this, we can see that the runtime in the worst case is f(n) = n, where n is the size of the list.

In the best case, our function only requires a single iteration of the loop to complete. In this case, the number of operations is constant. As we discussed previously, we often represent this as f(n) = 1, meaning that no matter what the size, n is, the number of operations does not change.

The average case requires some math to compute. In the average case, our item could be the first item, second item, third item, etc. It could also not be in the list. Let’s assume the item is uniformly distributed. The probability of finding our item at a particular index in this case is 1/n. If we average this probability, we find the series 1/n + 2/n + … + n/n. This series converges to (n+1)/2. This gives us our average case of n/2 + 1/2, or 1/2n + 1/2. Now, recall that we only want to pay attention to our highest order growth terms. This means we can drop the + 1/2 constant and the 1/2 multiplying n. This gives us f(n) = n or linear runtime.

Understand the case analysis, we can now formally discuss asymptotic analysis.

Applying Asymptotic Analysis

Let’s start by considering the worst case analysis of our algorithm. When we discuss the worst case of an algorithm in asymptotic notation, we will use a special notation called O-notation (read as Big O Notation). A function is said to be O(g(n)) if g(n) bounds the function above. In more formal terms:

Given two functions f(n) and g(n), we say f(n) = O(g(n)) if there exists constant values c > 0, a > 0, such that f(n)≤cg(n), for all n ≥ a.

What this basically means is that some constant multiple of g(n) will always be at least as big as our function. In other words, it act as an upper bound for our function. Since our function never goes above the upper bound, the upper bound describes its highest possible value, or worst case in the context of algorithm runtime.

Let’s return to our worst-case analysis of linear search briefly to contextualize this definition. I asserted that linear search has a worst case g(n) = n, which would mean it is O(n). If this is true, it means that 0 ≤ n ≤ cn, n ≥ a.

In this example, we can see that this is true for any c greater than 1, when a is greater than or equal to 1.

Now, remember how I said we could drop the constants in front of our function? This inequality explains why. Suppose we had a constant in front of g(n) = n (I’ll represent it as b). This would give us the following expression: 0 ≤ bn ≤ cn

No matter what b is, there exists some c = b+1 that satisfies this inequality. This is why we can drop the constant and simply say the worst case is O(n). A similar structure appears for both best case and average case. For the best case, we use a notation called Omega-notation. This represents the best case, so instead of an upper bound, we use a lower bound.

A function g(n) is said to be Ω(f(n)) if there exists some a, c, such that 0 ≤ cg(n) ≤ f(n) for all n ≥ a.

When we look at our linear search example, we saw that the best case was f(n) = 1. Stated more formally, we can find that 0 ≤ c(1) ≤ 1 for all n ≥ a.

For this example, we can see that for all n, setting c to 1 satisfies the inequality. Therefore, we can conclude our best case is Ω(1).

Finally, for the average case, we want to show that our function is somewhere between two functions. In our formal statement, A function g(n) is said to be θ(f(n)) if there exists some a, c1,c2, such that

0 ≤ c₁g(n) ≤ f(n) ≤ c₂​g(n) for all n ≥ a.

For our linear search example, we found our average case was n. Our original function was 1/2n + 1/2. We can show that this is θ(n) as follows: 0<=c1​n<=1/2n+1/2<=c2​n. If c1 is 1/4 and c2 is 2, we find that this is true for all n > 0.

In most cases, we are only going to focus on the worst case of an algorithm runtime. The reason for this is because we usually want to optimize the worst case of an algorithm, unless it happens infrequently. Doing this allows us to guarantee the efficiency of an algorithm. We will sometimes examine average and best case, specifically when they are relevant to a particular algorithm’s analysis.

You are going to see this type of notation and analysis frequently as you study algorithms and data structures. At first it may feel a bit odd or unintuitive. Don’t be concerned, as you practice, this type of analysis will become very clear. We will be sure to show step by step processes every chance we get to help solidify these concepts. With that being said, the next article in this series will jump into the world of data structures and algorithms!

To learn more about DSA in Python, check out our free Python DSA course.