In this video we will see how cProfile (default Python library) can help you to get run-times from your Python program.

Queue vs Python lists

In this video we will compare the performance of a simple Queue implemented directly into Python (no optimisations) with the default Python list.

Can it compare with it on performance?

This is where time complexity analysis come into the picture. A Queue insert and deletion is O(1) time complexity. A Python list used as a queue has O(n) time complexity.

But does the performance and run-time show the same? Here we compare the run-time by using cProfile in Python.

Want to learn more about Linked-lists, Stacks and Queues?

How to evaluate the time complexity of the Bubble sort algorithm

What is Bubble sort and how does it work?

In this video the Bubble sort algorithm is explained. On a high level, it takes an unsorted list and returns it sorted.

How to implement Bubble sort in Python

Well, notice the above description. It is straight forward and simple to implement. That is one of the beauties of the algorithm. Simple to understand. Simple to implement.

def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

An simple illustration of how you can use it.

import random
def generate_random_list(n):
my_list = []
for i in range(n):
my_list.append(random.randint(0, n))
return my_list
def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]
my_list = generate_random_list(20)
print(my_list)
bubble_sort(my_list)
print(my_list)

Evaluating the performance of Bubble sort

First of the algorithm has two for-loops. An outer and an inner for-loop. With an input of a list of length N, the loops will be iterated the following number of times.

Outer for-loop: N times

Inner for-loop: N-1 + N-2 + N-3 + … + 1 + 0 times

Knowing the formula

N-1 + N-2 + … + 1 + 0 = (N-1)*N/2

We can add that the time complexity of Bubble sort is O(n^2).

But let’s try to experiment with real running data, to see if we can confirm that complexity.

To get run-times from the algorithm the cProfile library comes in handy. It is easy to use and gives good insights. A simple way to get run-times is to set it like this.

import random
import cProfile
def generate_random_list(n):
return [random.randint(0, 4*n) for i in range(n)]
def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]
def profile_bubble_sort(n):
my_list = generate_random_list(n)
bubble_sort(my_list)
cProfile.run("profile_bubble_sort(10000)")

It will result in an output in the following manner.