I have written a recusive program for merge sort. How to analyze it's time complexity by plotting graph of its running time against input in python

Question

I have written a recusive program for merge sort successfully. How to analyze it's time complexity by plotting a graph of its running time against different inputs in python ?

Answer 1

You can write the code as below in Python: -

import time
from numpy.random import seed
from numpy.random import randint
import matplotlib.pyplot as plt

def MergeSort(a):
    /**
       YOUR MERGESORT IMPLEMENTATION
    **/

elements = list() # It contains the list of sizes of each input
times = list() # It contains the list of runtime against each input

# I am trying to analyze on 10 inputs, totally chosen randomly

for i in range(10):
  
    # generate some random integer list to be sorted
    a = randint(0, 1000 * i, 1000 * i)
    # there are multiple ways of calculating time complexity, I am using time module
    start = time.clock()
    MergeSort(a)
    end = time.clock()
 
    print(len(a), "Elements Sorted by MergeSort in ", end-start)
    elements.append(len(a))
    times.append(end-start)

plt.xlabel('Array Length')
plt.ylabel('Time Complexity')
plt.plot(elements, times, label ='Merge Sort')
plt.grid()
plt.legend()
plt.show()

There are multiple modules to analyze the time complexity of python code. You can refer to the below post: -

How do I get the time of a python programs execution