Python script using pyplot (Matlab-like) lib to demonstrate big-o complexities of standard algorithms. Big O notation is used to classify algorithms based on their time and space complexity.
- matplotlib
- pyqt5 (lib GUI)
pip install matplotlib
pip install pyqt5
First, we will initialize some numbers list to help to explain the different types of algorithms in Big O Notation.
numbersList = [1, 2, 3, 4, 5]
In this type, the execution time is independent of the size of the input and will always take the same amount of time to execute.
def constant(n):
print(n[0])
constant(numbersList) # Output: 1
This type of algorithm will have a linear time complexity and will run linearly with the input size.
def linear(n):
for i in n:
print(i) # Output: 1
linear(numbersList)
# Output:
# 1
# 2
# 3
# 4
# 5
An algorithm has quadratic time complexity if the time to execute it is proportional to the square of the input size. In a few words, think of Linear but squared
def quadratic(n):
for i in n:
for j in n:
print(i, j)
print('---')
quadratic(numbersList)
# Output:
# 1 1
# 1 2
# 1 3
# 1 4
# 1 5
# ---
# 2 1
# 2 2
# 2 3
# 2 4
# 2 5
# ---
# 3 1
# 3 2
# 3 3
# 3 4
# 3 5
# ---
# 4 1
# 4 2
# 4 3
# 4 4
# 4 5
# ---
# 5 1
# 5 2
# 5 3
# 5 4
# 5 5
# ---