Introduction
When developing algorithms we typically focus on its validity – in other words whether it can do the work it is supposed to. However, time and space complexity are two very important factors that must be evaluated in order to ensure that the algorithm can be implemented and used in practise.
Even though an algorithm may theoretically work, what happens if the time it takes to run it makes it useless? Or what if the space it requires is so large that the computer may run out of memory?
In today’s article, we will be discussing about time and space complexity in the context of asymptotic algorithm analysis. We will explore the Big O notation, which is the most commonly used metric that is used to describe the efficiency of algorithms.
Additionally, we will also discuss about the difference between the Big O, Big Theta and Big Omega notations. Finally, we will also work with a couple of hands-on examples in order to demonstrate how the time and space complexity can be calculated in practise.
Note that the examples will be in Python – even if you don’t know Python I am pretty sure it will be easier than you think to follow along. I made to sure to add as many comments as possible to help people with no Python background 🙂
Asymptotic Time Complexity
In mathematical analysis, asymptotic analysis is a method used to describe the value (i.e. the limit) that a function approaches as the input approaches some other value. As an example, let’s consider that we want to study the behaviour of a function f(n) as the number n becomes significantly large.
If f (n) = n⁴ + 4n + 10 and number n is very large, then the term 4n will be insignificant when compared to the term n⁴ while n has no impact over the constant 10. Therefore, the function f(n) is said to be asymptotically equivalent to n⁴ as n approaches infinite.
Now in the context of algorithms, asymptotic analysis is performed in order to describe or evaluate the performance of an algorithm in terms of the input size. In other words, we use asymptotic analysis to determine the time and space increase when the input size also increases.
As an example, let’s consider that you want to transfer a data file to a friend who lives in a city which is 3 hours away from your current location. Now let’s suppose that there are actually two ways for sending it over; the first is to transfer it electronically and the second one is to travel 3 hours and hand it over to her (physically) on a USB stick. If you decide to send over the file electronically, the transfer time will be affected by the file size. The larger the file is, the more time it will require to be transferred to your friend. On the other hand if you decide to travel to your friend’s location and hand it over, the transfer time will be 3 hours, independently to how small or large the file is and thus the file size will not affect the transfer time.
This behaviour is illustrated in the Figure below – O(s) corresponds to the time complexity in case you transfer the file electronically. As the file size s increases, time required to complete the transfer also increases (in this example this increase is linear). On the other hand, O(1) corresponds to the time complexity in the case of transferring the file physically and thus time complexity is constant.
Big O vs Big Theta vs Big Omega
The Big O notation is used to describe an upper bound of algorithms’ complexity. Let’s suppose we have a list (or array) of N integers. If we’d want to print out every element of the list the time complexity would be O(N). Theoretically though, the time complexity of this use-case could also be described as O(N²) or O(N³) or really any other Big O greater than O(N) since these are upper bounds.
This might be a little bit confusing so let’s consider a real-life example. Let’s make an assumption that no car can exceed the speed of 400 km/h. If we have a car with maximum speed X, then we can certainly say that X ≤ 400. Theoretically though, we could also say that X≤ 1,000 or X ≤ 10,000. Technically this is true because we work with upper bounds even though stretching the upper bound even further isn’t quite useful.
Apart from Big O there are however two alternative notations, namely Big Omega (Ω) and Big Theta (Θ).
Big Omega is used to describe lower bounds. Going back to our example with printing out all list elements, the lower bound would be Ω(N) given that we know that it won’t be faster than that. Likewise, we could also say that the lower bound is Ω(1) or Ω(logN) given that printing out a list with N elements won’t get any faster than these lower bounds.
Big Theta is used to describe tight bounds. This means that an algorithm can be described as Θ(N) if it is both O(N) and Ω(N). We could say that printing an array with N elements is Θ(N).
In general, we typically use the Big O notation to describe the time and space complexity of algorithms while always try to define the tightest runtime possible given the details we have for the particular algorithm and/or use-case.
Best Case vs Worst Case vs Expected Case
Various algorithms involve some form of randomness that may affect the performance of the algorithm. There are also algorithms that may run faster on sorted arrays but slower when the elements of the array are not ordered.
Therefore, there are actually three different ways in which we can describe the runtime of an algorithm; best case, expected case and worst case. When we evaluate the performance of algorithms the worst case complexity should be calculated.
Note that these concepts should not be confused with Big Theta and Big Omega we discussed earlier. Lower and upper bounds have nothing to do with best, worst and expected cases.
Space Complexity
Apart from time complexity, another important aspect that should be evaluated is space complexity which is the amount of memory that an algorithm requires in order to be executed. With the constantly evolving computer power, space complexity is usually overlooked by programmers. It is however very important to design and implement algorithms in a way that they consume the least possible amount of memory given that the data being processed are constantly evolving, too.
Going into the practical computation of space complexity, if we were about to create a one-dimensional array with N integers, then it would require O(n) space. Likewise, a two-dimensional array of size n x n would required O(n²) space. It is also important to mention here that apart of the space taken by elements in data structures, the space allocated to stacks in recursive calls should also be taken into account.
Calculating Space Complexity with Big O Notation
As an example, let’s consider the following recursive function that is used to compute the sum of the numbers between 0 and n:
def sum_func(n: int):
"""
Recursive method that returns the sum
of the numbers between 0 and input n
"""
if n > 0:
return sum_func(n - 1) + n return 0Even though the input to the function is just a single integer number, every recursive call adds an additional level to the call stack. For instance,
sum_func(5)
adds call sum_func(4) to stack
adds call sum_func(3) to stack
adds call sum_func(2) to stack
adds call sum_func(1) to stack
adds call sum_func(0) to stackIn practise, every call being added to the call stack consumes an actual memory and thus they should always be taken into account when computing space complexity. Therefore, the function sum_func will require O(n) time as well as O(n) space.
Having n calls though, does not necessarily mean that an algorithm will required O(n) space. Now let’s modify the recursive method that we’ve used earlier so that the computation of the sum between 0 and the input number n is computed in an iterative way.
def sum_func(n: int):
"""
Iterative method that returns the sum
of the numbers between 0 and input n
"""
sum = 0
for i in range(n+1):
sum = sum_nums(sum, i)
return sum
def sum_nums(a: int, b:int):
"""
Returns the sum of two numbers
"""
return a + bThe above function will take O(n) time and O(1) space. In other words, the memory required in order to execute the function sum_func is constant.
Calculating Time Complexity with Big O Notation
Now going back to time complexity, it is important to highlight the fact that the Big O notation does not correspond to the actual execution time of the algorithm in question. For example, an algorithm of O(n) may in fact be faster than an algorithm of O(1). Therefore, we can say that Big O is used to describe the rate of increase in relation to the input size.
This is the main reason why we don’t really pay attention to constants when it comes to calculating time complexity. In the very beginning, we discussed about asymptotic analysis in the context of Mathematics.
If f (n) = n⁴ + 4n + 10 and number n is very large, then the term 4n will be insignificant when compared to the term n⁴ while n has no impact over the constant 10. Therefore, the function f(n) is said to be asymptotically equivalent to n⁴ as n approaches infinite.
Similarly, in algorithmic asymptotic analysis we drop any constant values as well as insignificant terms.
As an example, let’s consider two versions of an algorithm that computes both the minimum and maximum numbers from an input list. Note that there may be way more elegant ways to perform the same actions but the purpose of this example is to demonstrate a couple of concepts related to Big-O notation.
def get_min_max(lst):
"""
Returns the minimum and maximum
numbers from the input list as a
tuple in the form (min, max)
"""
_min = lst[0]
_max = lst[0] for n in lst[1:]:
if n > _max:
_max = n
if n < _min:
_min = n return _min, _maxSince we have a single for-loop that goes through the elements of the input list, the time complexity of the function above can be described with O(n).
Now let’s modify this method such that the calculation of min and max numbers happens in separate loops.
def get_min_max(lst):
"""
Returns the minimum and maximum
numbers from the input list as a
tuple in the form (min, max)
"""
_min = lst[0]
_max = lst[0] for n in lst[1:]:
if n > _max:
_max = n for n in lst[1:]:
if n < _min:
_min = n return _min, _maxNow we have two separate (not nested though!) for-loops, each of which takes O(n) time to get executed. Somebody could argue that this is translated into O(n + n) and therefore O(2n). Recall though that when describing time complexity with Big-O notation, we must eliminate any constant and/or insignificant terms. Therefore, the complexity of the second version of our example algorithm is still O(n) as we are only interested in the rate of increase.
Let’s consider another example where a function takes an input list and it prints out the original elements as well as the squared elements (once again, I warn you that there are way more elegant ways to achieve the same so please don’t pay too much attention to the logic).
def print_squares(lst):
for a in lst:
print(a) for a in lst:
for b in lst:
print(a * b)So we have one for-loop that simply goes through the elements of the input list and prints every single one of them and then we have two nested loops.
The former expression requires O(n) time, while the latter requires O(n²) due to the two nested loops. Again, someone would argue that the time complexity is O(n² + n) but given that we are only interested in the rate of increase, we must drop any insignificant terms and thus we’ll end up with a time complexity of O(n²).
Rate of increase
The standard rates of increase that are used most of the times in order to describe time and space complexity of algorithms are listed below.
- Logarithmic: O(log n)
- Linear: O(n)
- Linearithmic: O(n log n)
- Quadratic: O(n²)
- Exponential: O(c^n) where c is a fixed value and c > 1
- Factorial: O(n!)
Final Thoughts
In today’s article we discussed the importance of evaluating both time and space complexity when developing algorithms. This can be achieved through asymptotic analysis, that can helps us describe the performance using the Big O notation.
Additionally, we discussed the difference between the Big O notation with Big Omega and Big Theta as well as the meaning of best, worst and expected case when it comes to describing algorithmic complexity. We also used some example algorithms in order to demonstrate how time and space complexity can be calculated. Finally, we had a quick look at the most commonly used rates of increase that would normally cover most of the cases when it comes to computing space and time complexity of an algorithm.
Asymptotic analysis in algorithms is a fundamental and very important topic that every single person who writes code must be aware of. By understanding how certain decisions affect time and space complexity, you can eventually improve the quality and performance of your code. Additionally, if you are looking into nailing your next interviews, then this is a topic that you must meticulously revise. The chances are you will be asked to develop an algorithm and both time and space complexity are concepts that you need to consider when doing so. Even if you don’t manage to implement the most optimal solution for a given problem, you should at least be aware of how your solution performs as well as how it can be modified to reach optimal complexity times.
Become a member and read every story on Medium. Your membership fee directly supports me and other writers you read. You’ll also get full access to every story on Medium.
Related articles you may also like
