— July 25, 2021
Use code to visualize and determine runtime complexities for different algorithms.
This article will cover how you can use visualization libraries and software to determine runtime complexities for different algorithms. We will cover the basic usage of
matplotlib for visualization of 2d plots and
numpy for calculating lines of best fit, and then go over how these libraries can be used to determine their runtime complexity either through "guesstimation" or by comparing the plots of their runtimes to that of known functions (i.e. y=x, y=2^n).
If you are interested in downloading the code featured in this article, please visit this repository on my GitHub (chroline/visualizingRuntimes).
Runtime complexity, more specifically runtime complexity analysis, is a measurement of how “fast” an algorithm can run as the amount of operations it requires increases. Before we dive into visualizing the runtimes of different algorithms, let’s look at a couple of basic examples to explain the concept.
Take the following
add function. It accepts two parameters,
b, and performs addition on
When given any two parameters (1 and 2, 2 and 3, 29347 and 93648), the amount of operations does not change. Therefore, we say the algorithm runs in constant, or O(1) , time.
However, now consider the following
permutations function. It accepts one main parameter,
string, and prints all of the permutations of that string.
As you could imagine, this function would take much longer than the previous
add function; in fact, this function would run in what is called factorial time, represented as O(n!). That is because as the amount of characters in
string increases, the amount of operations required to find all the permutations increases factorially.
When comparing the runtimes of two functions visually, you would notice a stark contrast in the graphs they produce. For the
add function, you would observe a flat line, as the input of the function does not affect the amount of operations required by the function. However, for the
permutations function, you would observe a line that drastically spikes upwards (the slope of the line would approach infinity) because the amount of operations increases factorially as the size of the input increases.
Now that we have covered the basics of runtime complexity analysis, we can begin the process of writing code to visualize the runtimes of different algorithms.
Before running any visualizations, we must first import the necessary libraries and initialize them.
matplotlibis a library that will create and display the graphs
numpyis a library that consists of numerous mathematical utility functions
timeitis a library that we will use to time how long each call to the algorithm takes
mathis the basic Python math library
randomis the basic Python randomization library
Below are some code segments that demonstrate how to use
sum function calculates the sum of all elements of a provided
Iterable. This function implements an algorithm with a O(n) runtime complexity.
To test this, we will use the
linspace method from the
numpy library to generate an iterable with 50 evenly-spaced values ranging from 10 to 10,000. The graph, although not a perfectly straight plot, illustrates this.
We can add a line of best fit (using a 4th-degree function) to further exemplify this. The graph will never be a perfectly straight-line, but it should come close.
Retrieving an item from a list (list indexing) runs with O(1) runtime complexity, which means that the amount of items in the list does not affect how long the algorithm takes to run. How is this represented in a graph?
Now we will look at the graphs produced by the following algorithms:
Linear search has a runtime complexity of O(n), which will be represented by an approximately straight line.
Red plots demonstrate searching for an element in a shuffled, blue plots demonstrate searching for an element that is not present in the list.
The line of best fit for the red plots will generally be lesser than that of the blue plots because searching for an element that is not present in the list requires iterating through the entire list.
Binary search runs with O(log n) runtime complexity.
Above is what the graph should look like in a near-perfect simulation. As you can see, there are some some outliers, and in a perfect simulation the line of best fit would be identical to a logarithmic function.
What runtime complexity does insertion sort have? We can use the plots of its runtime and compare those plots against the graphs of known runtimes to determine which is the closest match.
Now, we can compare that graph with graphs of different runtimes to ultimately determine which is most similar and which runtime complexity insertion sort has.
Red plots represent O(log n), blue plots represent O(n^2), green plots represent O(2^n)
Based on these graphs, it is safe to assume that insertion sort runs in O(n^2) time.
Can we use visualization of the runtimes of mystery functions to guesstimate their runtime complexities?
Without even comparing this graph to the graphs of the possible runtimes, we can already safely assume that this function operates in O(n) runtime.
This graph looks very similar to the one for insertion sort, so we can determine that this function has a runtime complexity of O(n^2).
This function is more ambiguous than the previous two. It is evident that its runtime must be greater than O(n) as the slope increases as n increases. Let's consider the graphs of runtimes O(n^2) in red and O(2^n) in blue.
The graph of the runtime of mystery function #3 more closely resembles the blue plots, so therefore the runtime complexity of mystery function #3 is O(2^n).
Using these visualization libraries, we are able to determine the runtime complexities of functions and algorithms by comparing them to plots/graphs of known runtimes (i.e. comparing plots of insertion sort runtime against y=n^2). In addition to determining runtime complexities, this methodology can be used to compare the speeds of different algorithms against each other. With only a few lines of code, you can quickly see the speed at which your chosen algorithms will run with large sets of data!
Don’t miss out on the latest content! Join over 3k+ devs in subscribing to Instructive.dev.
Join the mailing list