Introduction
There are usually multiple ways to solve the problem using a computer program. For instance, there are several ways to sort items in an array - you can use merge sort, bubble sort, insertion sort, and so on. All of these algorithms have their own pros and cons and the developer's job is to weigh them to be able to choose the best algorithm to use in any use case. In other words, the main question is which algorithm to use to solve a specific problem when there exist multiple solutions to the problem.
Algorithm analysis refers to the analysis of the complexity of different algorithms and finding the most efficient algorithm to solve the problem at hand. Big-O notation is a statistical measure used to describe the complexity of the algorithm.
In this guide, we'll first take a brief review of algorithm analysis and then take a deeper look at the Big-O notation. We will see how Big-O notation can be used to find algorithm complexity with the help of different Python functions.
Note: Big-O notation is one of the measures used for algorithmic complexity. Some others include Big-Theta and Big-Omega. Big-Omega, Big-Theta, and Big-O are intuitively equal to the best, average, and worst time complexity an algorithm can achieve. We typically use Big-O as a measure, instead of the other two, because it can guarantee that an algorithm runs in an acceptable complexity in its worst case, it'll work in the average and best case as well, but not vice versa.
Why is Algorithm Analysis Important?
To understand why algorithm analysis is important, we will take the help of a simple example. Suppose a manager gives a task to two of his employees to design an algorithm in Python that calculates the factorial of a number entered by the user. The algorithm developed by the first employee looks like this:
def fact(n):
product = 1
for i in range(n):
product = product * (i+1)
return product
print(fact(5))
Notice that the algorithm simply takes an integer as an argument. Inside the fact() function a variable named product is initialized to 1. A loop executes from 1 to n and during each iteration, the value in the product is multiplied by the number being iterated by the loop and the result is stored in the product variable again. After the loop executes, the product variable will contain the factorial.
Similarly, the second employee also developed an algorithm that calculates the factorial of a number. The second employee used a recursive function to calculate the factorial of the number n:
def fact2(n):
if n == 0:
return 1
else:
return n * fact2(n-1)
print(fact2(5))
The manager has to decide which algorithm to use. To do so, they've decided to choose which algorithm runs faster. One way to do so is by finding the time required to execute the code on the same input.
In the Jupyter Notebook, you can use the %timeit literal followed by the function call to find the time taken by the function to execute:
%timeit fact(50)
This will give us:
9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
The output says that the algorithm takes 9 microseconds (plus/minus 45 nanoseconds) per loop.
Similarly, we can calculate how much time the second approach takes to execute:
%timeit fact2(50)
This will result in:
15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
The second algorithm involving recursion takes 15 microseconds (plus/minus 427 nanoseconds).
The execution time shows that the first algorithm is faster compared to the second algorithm involving recursion. When dealing with large inputs, the performance difference can become more significant.
However, execution time is not a good metric to measure the complexity of an algorithm since it depends upon the hardware. A more objective complexity analysis metric for an algorithm is needed.
This is where the Big O notation comes into play!
Algorithm Analysis with Big-O Notation
The Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.
It is denoted by a capital "O" followed by an opening and closing parenthesis. Inside the parenthesis, the relationship between the input and the steps taken by the algorithm is presented using "n".
The key takeaway is - the Big-O isn't interested in a particular instance in which you run an algorithm, such as
fact(50), but rather, in how well it scales given increasing input. This is a much better metric for evaluating than concrete time for a concrete instance!
For example, if there is a linear relationship between the input and the step taken by the algorithm to complete its execution, the Big-O notation used will be O(n). Similarly, the Big-O notation for quadratic functions