Big O Notation in Python

Table of content

• Big O Notation in Python
• Time Complexities

Considering the sheer amount of data processed nowadays, the time and space used by algorithms should be efficient.

Computational Complexity is the study of algorithms on the basis of the number of resources it requires to operate. Time Complexity is a method to calculate the amount of time an algorithm requires to run.

Big O Notation is also called Asymptotic Notation. It is a mathematical notation that describes the study of the limiting nature of a function when the arguments tend towards a value or infinity.

Why do we need Big O Notation?

Big O Notation is used to analyze algorithms on the basis of the increase in the time they take to run with an increasing input size (denoted by n). Thus functions with the same growth rates will have the same Big O notations.

It mathematically describes the upper bound or worst-case scenarios of algorithm time complexities and compares them.

Definition

If g and f are functions on natural numbers, the function f is O(g) or Big O of g, if and only if there exists a constant c > 0 and a natural number n0 such that f(n)≤c.g(n) ∀ n ≥ n0 . Summary of the common Time Complexities

Some common Time Complexities which will be discussed are as follows:

Graphical Representation of Time Complexities

Constant Time or O( 1 )

When the time elapsed to run an algorithm does not depend on the number of input data being processed, the algorithm is said to follow Constant Time. For such algorithms, the running time remains the same irrespective of the number of data being processed.

For example, in Python 3:

def display( array ):
    print(array[0])
a = [1, 2, 3, 4, 5]
display(a)

This prints the first member of the array irrespective of the length of the array is passed. Thus it is independent of the array length.

Algorithms with constant time complexities are the best as the length of the arrays does not affect the running times of these algorithms.

Logarithmic Time or O( log n )

An algorithm that reduces the number of input data with every step follows logarithmic time complexity. This complexity is usually followed by Binary Trees or Binary Search mechanisms. The Binary Search Python 3 code is as follows

def BinarySearch(array,st, sp, search):
    mid = int((st+sp)/2)
    if array[mid] == search:
        print(mid)
    elif array[mid] > search:
        if mid-1 >= st:
            BinarySearch(array, st, mid-1, search)
        else:
            print("Element Not Found!")
    elif array[mid] < search:
        if mid+1 <= sp:
            BinarySearch(array, mid+1, sp, search)
        else:
            print("Element Not Found!")

Linear Time or O( n )

Linear Time Complexity is followed when the amount of time required for an algorithm to run increases linearly with the number of data being processed. This is the best time one can obtain in case all the elements of the input data need to be accessed.

The following code is the Python 3 code for Linear Search which follows Linear Time:

def LinearSearch(array, search):
    i = 0
    while i < len(array):
        if array[i] == search:
            print(i)
            flag = 1
            break
        else:
            flag = 0
            i = i + 1
    if flag == 0:
        print("Element not Found!!!")

In this code snippet, all the values of the array being passed are accessed for processing.

Quasilinear Time or O( n log n )

An algorithm adapts quasilinear time complexity when each process in the input data has logarithmic time complexity. Sorting algorithms like merge and heap sort follow this complexity.

Quasilinear time is represented in the following code example by defining the Merge Sort function:

def merge(list2, le, m, ri):
	n1 = m - le + 1
	n2 = ri- m
	L = [0] * (n1)
	R = [0] * (n2)
	for i in range(0 , n1):
		L[i] = list2[le + i]
	for j in range(0 , n2):
		R[j] = list2[m + 1 + j]
	i = 0	 
	j = 0	 
	k = le	 
	while i < n1 and j < n2 :
		if L[i] <= R[j]:
			list2[k] = L[i]
			i += 1
		else:
			list2[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		list2[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		list2[k] = R[j]
		j += 1
		k += 1
def mergeSort(list1, le, ri):
	if le < ri:
		m = (le+(ri-1))//2
		mergeSort(list1, le, m)
		mergeSort(list1, m+1, ri)
		merge(list1, le, m, ri)

The merge sort method can be pictorially represented as:

Quadratic Time or O( n² )

An algorithm that follows linear time complexity for each of its input elements, is said to follow Quadratic Time Complexity. The Bubble Sort algorithm is an example of an algorithm that follows quadratic time as each of its elements is compared to all the other elements.

The following is a Python 3 code for the Bubble Sort Algorithm:

def BubbleSort(array):
    i = len(array) - 1
    while i > 0:
        j = 0
        while j+1 <= i:
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
            j = j + 1
        i = i - 1
    return array

Exponential Time or O( 2ⁿ )

When the growth in time elapsed during processing doubles with the inclusion of every new input element, it is said to be in Exponential Time Complexity.

Brute Force algorithms often exhibit exponential time complexities. The recursive calculation of Fibonacci Numbers is an example of an algorithm in Exponential Time.

The Python 3 code is as follows:

def Fibonacci(n):
    if n <= 1:
        return 1
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

Factorial Time or O( n! )

An algorithm that grows factorially with each increase in input element is said to follow Factorial Time. Heap's method is an example that follows such a complexity.

Recommended Readings

• Introduction to Data Structures in Python
• Lists in Python
• Tuples in Python
• Dictionaries in Python
• Heaps in Python
• AVL Trees using Python
• Recursion in Python
• Binary Search Tree using Python