A Beginner’s Guide to Big O notation

What is a Big O notation? Big O notation(“O” stands for “order”) is the language we use in Computer Science to describe the performance of an algorithm.

How to quantify the performance of an algorithm? We could quantify it by(i)time cost and (ii) space cost. For time cost, Big O notation describes how much runtime an algorithm takes to run as the size n of input data set increases. In other words, Big O notation shows how quickly the runtime of executing an algorithm grows in “worst case”. For space cost, Big O notation describes how large of additional space(relative to the size n of input data set) an algorithm needs.

Why do we need “Big O” notation? In order to choose the suitable algorithm for the problem we want to solve. For example, if we want to sort a list, and here are different algorithms to accomplish this task(e.g. Merge Sort, Quick Sort, Bubble Sort). In order to compare the efficiency of different algorithms, we use “Big O” notation. Sometimes we will choose an algorithm that occupies less space but more time if additional space is very expensive to the company.

Here are some examples we could look at for each time complexity. All the examples are shown in Python.

Time Complexity: O(1)

Name: Constant

Example operations: append, get item, set item.

# Append an element to a list
myList = [ ]
myList.append(666)
print myList
# return [666]

Time Complexity: O(log n)

Name: Logarithmic

Example operations: Finding an element in a sorted array.

# Find target 22 (i.e. return its index)in a sorted list
# Here we use Binary Search algorithm because its time complexity is O(log n)
def binarySearch(sortedList, target):
 left = 0
 right = len(sortedList) - 1
 while (left <= right):
  mid = (left + right)/2
  if (sortedList(mid) == target):
   return mid
  elif(sortedList(mid) < target):
   left = mid + 1
  else:
   right = mid - 1
# If target is not in the list, return -1
 return -1
binarySearch([1,3,9,22],22)
# return 3

Time Complexity: O(n)

Name: Linear

Example operations: copy, insert, delete, iteration.

Here is another example of the same operation — Finding an item in a sorted list. This algorithm is intuitively less efficient than binary search.

# Find target 22 (i.e. return its index)in a sorted list
def linearSearch(sortedList, target):
  for i in range(len(sortedList)):
    if (sortedList[i] == target):
    return i
# If target is not in the list, return -1
  return -1
linearSearch([1,3,9,22],22)
# return 3

Time Complexity: O(nLog n)

Name: Linear-Logarithmic

Example operations: Sort a list, for example, merge sort.

# Merge sort
def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        leftHalf = alist[:mid]
        rightHalf = alist[mid:]
        mergeSort(leftHalf)
        mergeSort(rightHalf)
        i=0
        j=0
        k=0
        while i < len(leftHalf) and j < len(rightHalf):
            if leftHalf[i] < rightHalf[j]:
                alist[k]= leftHalf[i]
                i=i+1
            else:
                alist[k]=rightHalf[j]
                j=j+1
            k=k+1
        while i < len(leftHalf):
            alist[k]=leftHalf[i]
            i=i+1
            k=k+1
        while j < len(rightHalf):
            alist[k]=rightHalf[j]
            j=j+1
            k=k+1
alist = [11,22,55,44,77,66,44,33,88]
mergeSort(alist)
print(alist)

Time Complexity: O(n²)

Name: Quadratic

Example operations: Find the shortest path between two nodes in a graph. Nested loops.

# Nested loops - pseudo code
for (list in list_groups):
    for (word in work_list):
        if (word == target_word):
            return 1
return -1

Time Complexity: O(n³)

Name: Cubic

Example operations: Matrix multiplication.

# 3 loops - pseudo code
for (i in range1):
    for (j in range2):
         for (k in range 3):
           if (aList[k] == target_word):
               return 1
     return -1
return -1

Time Complexity: O(2^n)

Name: Exponential

Example operations: ‘Towers of Hanoi’ problem, backtracking.

# Recursive calculation of Fibonacci numbers
def fibonacci(num):
    if (num <= 1):
       return num
    return fibonacci(number - 2) + fibonacci(number - 1)

Here is more information about Fibonacci numbers.

Reference: “Python Data Structures and Algorithms” by Benjamin Baka