How to find the Time Complexity of a Python Code

What is Time Complexity and Why it is important?

To explain in simple terms, Time Complexity is the total amount of time taken to execute a piece of code. This piece of code could be an algorithm or merely a logic which is optimal and efficient. Time complexity is a measure that determines the performance of the code which thereby signifies the efficiency of the same. It is always a good practice to think about the performance while writing the code.

Note: The lesser the time complexity of the code means the faster execution of it.

As a programmer, I am always concerned about the performance of my code and recently I came across a python module called ‘big-O’ that just made the work so easy. You can find the complete documentation of the package at https://pypi.org/project/big-O/

Big Thanks to the creator 👍

What is Big-O?

Basically, Big-O notation signifies the relationship between the input and the code, and some of the common Big-O functions are as follows:

Let's look into a few functions for a basic understanding.

A Constant complexity means that the time taken to execute the code remains constant irrespective of the input given. Similarly, Linear complexity means that the complexity increases ideally with the number of inputs. A possible example of this could be finding the largest number in a list of numbers given. With this understanding, we will move on to how to find the complexity of the code using the ‘big-O’ python module

1. Installation:

pip install big-O

2. Sample Python Code:

I have created a simple python function, which takes a string as an input and returns the first non-repetitive character in the string.

• I have used big-o inbuilt datagen to generate a set of random strings of length 100 (It also supports other generic datatypes)
• The parameter n_measures defines the number of inputs that need to be passed to the function
• You can also add a parameter n_times to specify the number of times the function is called to compute execution time

import big_o

#Generating random test strings of length 100
sample_strings = lambda n: big_o.datagen.strings(100)
#my logic to find the first non-repetitive character in the string
def non_repetitive(sample_string):
    string_list = list(sample_string)
    non_repetitive_char = next((ele for ele in string_list if string_list.count(ele)==1),None)
    return non_repetitive_char
#Calculating the Time complexity
best, others = big_o.big_o(non_repetitive, sample_strings,n_measures=20)
print(best)

The output of the above script is:

Constant: time = 2E-05 (sec)

This returns the best time complexity of my sample code along with the total time of execution. You can also look into the other time complexities by iterating through the second argument ‘others’ in the code.

for class_, residuals in others.items():
print(class_)
#output
Constant: time = 2.2E-05 (sec)
Linear: time = 2.9E-05 + -1.3E-10*n (sec)
Quadratic: time = 2.4E-05 + -6.2E-16*n^2 (sec)
Cubic: time = 2.3E-05 + -3.6E-21*n^3 (sec)
Polynomial: time = -8.9 * x^-0.19 (sec)
Logarithmic: time = 9.1E-05 + -6.7E-06*log(n) (sec)
Linearithmic: time = 2.8E-05 + -1E-11*n*log(n) (sec)
Exponential: time = -11 * -3.7E-06^n (sec)

I personally liked this module and thought it is worthy of sharing. I hope it will help you as well!!

References:

1. https://pypi.org/project/big-O/
2. https://stackabuse.com/big-o-notation-and-algorithm-analysis-with-python-examples/#:~:text=Big%2DO%20notation%20is%20a%20metrics%20used%20to%20find%20algorithm,by%20opening%20and%20closing%20parenthesis.