How to Make Your Code Run Faster: Time Complexity of the Built-in Python Functions
Selecting built-in functions wisely can make your algorithms or scripts run more efficiently. In other words, it reduces the time complexity, Big O, significantly.
Let’s do a quick recap about time complexity. If you are already familiar with this concept, feel free to skip to the main section.
In short, time complexity measures the time your algorithm or program needs to perform relative to the size of the input, which is can be an array, string, or number. For example, as the number of elements in your array increases, we want to know how is the behavior of the computation time.
Let’s investigate the following functions.
We see that the for loop iterates through all the elements in a list A, before doing the computation sum_A += i . Therefore as the number of elements of A goes up, the computation time should go up proportionately.
We represents time complexity with Big O, O() . The time complexity of the function above will be categorized as a complexity class O(N) , which means the computation time increases linearly as the size of the input increases. For example, if it takes 10 seconds to handle an input of 3 elements, it will roughly take 20 seconds to handle an input of 6 elements, and so on.
The best scenario is when we have O(1) complexity class, where computation time won’t change as the input size increases. And we can have O(N^2) or more, which means, as you can guess, the computation time increases exponentially as the input size increases.
Also note that when we refer to complexity here, we generally refer to the worst case time complexity, which is different from space complexity that measures the memories used.
That’s a very long recap about complexity. There are plenty of resources about the concept you can take a look, for example [1] and [2].
How complex is the built-in python functions?
Here we summarize the time complexity of some of the most useful Python built-in functions. These tables are based on the lecture note Complexity of Python Operation by University of California, Irvine.
List & Tuple
Set
Dictionary
Now let’s solve a problem together
Problem 1: At a conference, a stage time table is represented by a list A, where the value of A at index his the company name of the speaker who speak at hour index h.
The example below means that a speaker from Amazon will start at the second hour after a speaker from Google, and so on.
A[0] = “Google”
A[1] = “Amazon”
A[2] = “Facebook”
A[3] = “Amazon”
A[4] = “Microsoft”
A[5] = “IBM”
A[6] = “Apple”
A[7] = “Microsoft”
Note that this is just an example, and there can be more hours and company names. We denote its length as N.
Find the earliest time in hours when at least one representative each of all companies have presented on the stage.
In side the for loop of length N, we have a list slicing that costs O(i-0) with a set construction that costs O(len(A[:i])) with a check that cost O(len(A[:i])) .
Let’s look at another alternative solution
In side the for loop for length N, we have a discard function that costs only O(1) and a length function that costs O(1) .
Let’s see the compare their computation times
Here I tested both functions with different number of input, using numpy.arange(0, i) where i is 1 to 100. This is to test the worst computation time where the solution will return at the last iteration.
You can see here that a tiny tweak in your code means something.
Conclusion
Writing an efficient algorithm requires an understanding of the concept of Time Complexity. The easiest way to reduce the time complexity is to avoid a for loop whenever possible. Ideally, you may want to check the time complexity of time Python functions you use, and refactor your code by selecting the less complex functions. In addition to this, make sure you write a unit testing to guarantee that your functions work as expected.
