Finding time-complexity of algorithms

Today we will analyze the time-complexity of algorithms in Python. To do this, we must determine the overall time necessary to perform the required algorithm for various inputs.

The method we’re using is quick-sort, but you may experiment with an algorithm to determine the time-complexity of algorithms in Python.

Importing Modules/Libraries

The time module is required to determine how much time elapses between command executions. The random module is then used to produce random numbers for our original collection of integers to be sorted.

The algorithms module is used to directly obtain the quicksort code. You can also apply your own algorithm in this case.

import time
from random import randint
from algorithms.sort import quick_sort

Generating List for Quick-Sort

Now that we’ve imported all of our libraries, we can begin writing code. We’ll start with an unsorted array of items. The randint() method is used for this. The code below will generate a list of 20001 random numbers ranging from 0 to 999.

l = [randint(0,1000) for i in range(20000)]

Computing time complexity of the Algorithm

We begin by making an empty list in which we will store all of our time values for various inputs.

Then we execute a for-loop with a varying amount of inputs for each iteration. For each iteration, we first save time before running the algorithm. The quicksort method is then executed, with the number of elements growing with each iteration.

When the algorithm is finished, we store the end time and subtract it from the start time to get the time elapsed. The elapsed time is subsequently added to our collection of times.

times=[]
for x in range(0,20001,100):
    start_time = time.time()
    list2 = quick_sort(list1[:x])
    elapsed_time = time.time() - start_time
    times.append(elapsed_time)
print(times)

The output of the time consumed at each iteration is displayed below.

[5.9604644775390625e-06, 0.0003139972686767578, 0.00667881965637207, 0.001209259033203125, 0.0015976428985595703, 0.0021779537200927734, 0.0068056583404541016, 0.005601644515991211, 0.005861520767211914, 0.011028051376342773, 0.011818647384643555, 0.012465715408325195, 0.012626171112060547, 0.008950948715209961, 0.030421972274780273, 0.019321203231811523, 0.01583099365234375, 0.03421354293823242, 0.026609182357788086, 0.017530202865600586, 0.019039630889892578, 0.0118560791015625, 0.013288259506225586, 0.012446880340576172, 0.015150070190429688, 0.012840032577514648, 0.014685630798339844, 0.015198230743408203, 0.016430377960205078, 0.0168306827545166, 0.018042564392089844, 0.020036935806274414, 0.018283843994140625, 0.019774913787841797, 0.01965475082397461, 0.024692058563232422, 0.02126765251159668, 0.02456188201904297, 0.024203062057495117, 0.022081613540649414, 0.025351285934448242, 0.02523493766784668, 0.027686119079589844, 0.026891231536865234, 0.04227614402770996, 0.025140047073364258, 0.0282745361328125, 0.028072357177734375, 0.04300737380981445, 0.049503326416015625, 0.039911508560180664, 0.031244993209838867, 0.03950953483581543, 0.0483095645904541, 0.05027508735656738, 0.04074549674987793, 0.05907034873962402, 0.035933732986450195, 0.03742861747741699, 0.053351640701293945, 0.07302188873291016, 0.04110312461853027, 0.038227081298828125, 0.04067420959472656, 0.04362940788269043, 0.06206393241882324, 0.048111915588378906, 0.054494619369506836, 0.055097103118896484, 0.046785593032836914, 0.046590566635131836, 0.04422330856323242, 0.07317423820495605, 0.04566597938537598, 0.05501079559326172, 0.07018637657165527, 0.12341713905334473, 0.08685779571533203, 0.1301746368408203, 0.05524754524230957, 0.05509376525878906, 0.051004648208618164, 0.10072588920593262, 0.09502077102661133, 0.17278599739074707, 0.18680071830749512, 0.08754134178161621, 0.0879063606262207, 0.18670082092285156, 0.21729803085327148, 0.1556401252746582, 0.07978129386901855, 0.033004045486450195, 0.03307485580444336, 0.03363752365112305, 0.03286147117614746, 0.03313589096069336, 0.0342717170715332, 0.03235769271850586, 0.0335690975189209, 0.0449981689453125, 0.03151226043701172, 0.036780595779418945, 0.03641867637634277, 0.034799814224243164, 0.035429954528808594, 0.03528714179992676, 0.03522825241088867, 0.03563570976257324, 0.03550863265991211, 0.03803896903991699, 0.037568092346191406, 0.039276123046875, 0.05381584167480469, 0.04004693031311035, 0.040352582931518555, 0.04136157035827637, 0.041423797607421875, 0.045130014419555664, 0.04460620880126953, 0.04532432556152344, 0.04130244255065918, 0.04760575294494629, 0.04321622848510742, 0.046456336975097656, 0.04538416862487793, 0.04726004600524902, 0.04443860054016113, 0.04362082481384277, 0.04554152488708496, 0.046132802963256836, 0.0486757755279541, 0.046370744705200195, 0.04680061340332031, 0.04824686050415039, 0.06405234336853027, 0.0478060245513916, 0.04948878288269043, 0.049854278564453125, 0.05359053611755371, 0.05414247512817383, 0.05222964286804199, 0.051342010498046875, 0.05304098129272461, 0.06159520149230957, 0.0521693229675293, 0.05106377601623535, 0.054935455322265625, 0.053060054779052734, 0.052790164947509766, 0.05505990982055664, 0.057706356048583984, 0.05939984321594238, 0.060530900955200195, 0.07836294174194336, 0.06412434577941895, 0.05772709846496582, 0.060724735260009766, 0.05914807319641113, 0.0632481575012207, 0.059748172760009766, 0.06452727317810059, 0.06497621536254883, 0.06197404861450195, 0.06228804588317871, 0.06296825408935547, 0.06248354911804199, 0.06389427185058594, 0.06646037101745605, 0.06796479225158691, 0.08311891555786133, 0.065704345703125, 0.06447386741638184, 0.06992769241333008, 0.06401872634887695, 0.06702852249145508, 0.06934690475463867, 0.06805992126464844, 0.0670771598815918, 0.06830120086669922, 0.0785529613494873, 0.06986260414123535, 0.07060122489929199, 0.07129216194152832, 0.08096432685852051, 0.07953071594238281, 0.08166289329528809, 0.0758814811706543, 0.07543277740478516, 0.07652783393859863, 0.07634139060974121, 0.08227705955505371, 0.07456398010253906, 0.0725564956665039, 0.0724172592163086, 0.0800638198852539, 0.07935881614685059, 0.07793021202087402, 0.09217333793640137, 0.07755923271179199, 0.07942557334899902]

To plot the graph, we additionally require the number of inputs at each iteration.

x=[i for i in range(0,20001,100)]

Plotting the time value computed

It is now time to examine our findings. Let us draw a graph with the number of inputs on the x-axis and time on the y-axis.

import matplotlib.pyplot as plt
plt.style.use("seaborn")
plt.xlabel("No. of elements")
plt.ylabel("Time required")
plt.plot(x,times)
plt.show()

Conclusion

Congratulations! You just learned how to find the time complexity of algorithms. Hope you enjoyed it! 😇

Liked the tutorial? In any case, I would recommend you to have a look at the tutorials mentioned below:

Thank you for taking your time out! Hope you learned something new!! 😄