Every algorithm comes with its own complexities, and to analyze an algorithm we inspect two of these: the space complexity and the time complexity. The time complexity indicates the expected runtime as a function of the length of the input. Similarly the space complexity measures the amount of memory taken as a function of the length of the input.

The actual amount of time or space it takes to execute the algorithm is not the main concern here, we are going to remove as many factors as possible. We are going to assume that a certain operation is going to take a constant time, and the only thing that changes the time complexity is the amount of these constant operations we execute. Let’s consider the following algorithm to check if an element exists in a given array:

1def contains(x, data):
2    for element in data:
3        if element == x: 
4            return True
5    return False

If every comparison in the above code is taking up a constant time, the time complexity can be described by the element we are looking for: $x$. The amount of comparisons executed can be visualized if we track them in code as follows:

 1def countComparisons(x, data):
 2    count = 0
 3    for element in data:
 4        count += 1
 5        if element == x: 
 6            return count
 7    return count
 8
 9data = range(0, 10)
10print(countComparisons(0, data))
11print(countComparisons(10, data))
12print(countComparisons(1000, data))

When analyzing algorithms we usually consider the worst case scenario. When running the above code this scenario is clear: the amount of comparisons is the largest when $x$ is not in the array. The total execution time will then be the constant time for a comparison multiplied by the amount of comparisons: in this case the length of the array. The amount of operations executed in the algorithm is referred to as $n$.

We will use $n$ to determine some bounds of the function to reason about its runtime. These bounds are known as asymptotic bounds which are lines that bound a certain curve. There are three asymptotic notations that are relevant for this: $O$, $\Omega$ and $\Theta$. They are the asymptotic- upper bound, lower bound and tight bound respectively. $O$ (pronounced as “big O”) bounds the function on the upper bound, which is the worst case scenario we are looking for.

Order of growth

Comparing algorithms can be done rather easily if you know the order of growth. Knowing the order of growth allows you to calculate in advance how much more calculations have to be executed when increasing $n$. We express the order of growth in one of the above mentioned asymptotic bounds. Going back to the first example we can express the upper limit of this function as follows:

We say $O(n)$ to indicate that it’s a linear function: it grows linearly with the input size. If we were to increase the array size in the example, you can see that in the worst case the amount of comparisons will be no larger than a multiple of $n$. Here is a list of common bounds:

• Constant: $O(1)$
• Logarithmic: $O(log(n))$
• Linear: $O(n)$
• Quadratic: $O(n^2)$
• Polynomial: $O(n^a)$
• Exponential: $O(a^n)$
• Factorial: $O(n!)$

Where $a$ is some constant. Note that we are only interested in the largest increasing factor. The actual linear function would be in the format of $an + b$ where the constants $a$ and $b$ do not really matter since the upper bound will still scale linearly with n regardless.

For the next couple of examples, try to estimate the upper bound of the algorithms. The answers are listed at the bottom of the article.