Time Complexity and Big O Notation

Introduction

In computing, two important fundamentals that are important to understand are Time Complexity and Space Complexity. They are important because they allow us to compare efficiency of different algorithms that are meant to do the same task.

With analysis of Time Complexity and Space Complexity, we will be able to select the best algorithm for solving a specified problem. After all, what use is an algorithm which is so costly in terms of time and space?

Today, I will discuss Time Complexity. I will aim at simplifying the understanding of Time Complexity and prove to you that this hitherto complicated terminology can be easily decoded. In most cases, it is very easy to measure Time Complexity by just looking at the algorithm or code.


Algorithms

Time Complexity is based upon algorithms, which is a finite sequence of well-defined instructions required to solve a problem.

The following algorithm (in pseudocode) allows a user to input two numbers, a and b, calculates the sum, and returns it as c.

input a
input b
store a + b in c
return c

An algorithm must be unambiguous, finite, efficient, and language-independent. In real life, if a solution to a problem can be broken down into logical steps, then that problem is solvable computationally. An algorithm is written using basic code constructs such as loops (for, while, etc) and conditional flows (if, switch, etc).

Two of the most common algorithms in computing are sort and search. When dealing with data and/or databases, it is common to sort and search the retrieved data. For instance, all the following require sorting and searching algorithms under the hood:

• sorting/searching list of files
• sorting/searching list of domain user accounts
• searching within a text file
• sorting/searching customer list
• sorting/searching bank account names
• sorting/searching Facebook account names
• and the mother of it all: Google Search
• logging into a system e.g. email, etc requires the system to search for your login name
  
• etc, etc

If you were not convinced before, then the above list should convince you as to why sort and search algorithms are always emphasized in computer science classes. It is because we use them all the time. There is a lot of search and sort going on under the hood in our everyday use of computing devices, more so with the mobile devices that we use all the time.

In practice, we are only fortunate that in almost all cases, programming languages already have built-in functions that do efficient data sorting and searching. Nonetheless, it is still very important to understand searching and sorting algorithms from first principles. This kind of understanding helps us when dealing with other algorithmic assignments.

Time complexity is the amount of time taken by an algorithm to run as a function of the length of the input (n). It measures the time taken to execute each statement of code in an algorithm.


Big O

Time complexity is measured using the Big O Notation: O(1), O(n), etc – which is the worst case scenario. It is a measure of an algorithm’s efficiency. How well does an algorithm perform in the worst case scenario. Big O shows us how an algorithm slows down as input size increases.

Big O does not measure absolute time (but number computations) required by an algorithm. It doesn’t matter what kind of computer one is using, or how many other processes are running on the computer.

Let us look at an example of Linear Search algorithm, where a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

For example, to search for the number 2 from the array [3,1,5,7,9,4,2], we have n=7. Using linear search algorithm, we have to do n comparisons before we find 2.

To search for the number 8 from the same array above, we also have to do n comparisons before we find conclude that 8 is not in the list.

To search for the number 3 from the same array above, we have to do only one comparison before we find 3.

Therefore, the worst case of a linear search is n comparisons (computations), i.e. Time Complexity is O(n).

I will now show practical examples of Constant, Linear and Quadratic Time Complexities using pseudocode. These are examples taken from code that we use on a day-to-day basis while programming.

Rule: Since Time complexity is a function of n, we find the fastest growing term, and remove the coefficient to get Big O.


Constant Time (Least complex) – O(1)

Example 1:

initialize a –> O(1)
initialize b –> O(1)
c = a + b –> O(1)
Total Time =  O(1) + O(1) + O(1) = 3 * O(1) = O(1) after dropping constants

Example 2:

a = element with index 0 –> O(1)
b = element with index 100 –> O(1)
c = a + b –> O(1)
return c –> O(1)
Total Time =  O(1) + O(1) + O(1) + O(1) = 4 * O(1). Note that O(1) is a constant.
= 4 X c
= c
= O(1)

Linear Time – O(n)

Print title –> O(1)
loop through elements in a list of size n
      print current element –> O(1)

Total Time = –> O(1) + n X O(1). Note that O(1) is a constant.
= c1 + n X c2 + c3
= c + n X c2
Find the fastest growing term, and remove the coefficient
= n
= O(n)

Quadratic (Polynomial) Time – O(n**c)

Common cases are nested loops. Worse than Linear Time Complexity. E.g. bubble sort.

loop through elements in a list of size n
      loop through elements in a list of size n
            print current element in list 1 and 2 –> O(1)

Total Time = n X n X O(1) = O(n**2). Polynomial can be n3, n4, etc

Logarithmic Time – O(log n)

Binary search is a good example of Logarithmic Time Complexity, O(log n). Logarithmic Time Complexity is better than Linear but worse than Constant Time Complexity. To diversify a bit, I will demonstrate Logarithmic Time Complexity using the following Python code for recursive binary search.

# Python 3 program for recursive binary search.
 
# Returns index of x in arr if present, else -1
def binary_search(arr, low, high, x):
 
    # Check base case
    if high >= low:
 
        mid = (high + low) // 2
 
        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
 
        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
 
        # Else the element can only be present in right subarray
        else:
            return binary_search(arr, mid + 1, high, x)
 
    else:
        # Element is not present in the array
        return -1
 
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
# Function call
result = binary_search(arr, 0, len(arr)-1, x)
 
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

Exponential Time – O(c**n)

Worse than Polynomial (e.g. 2**n, 10**n). E.g. count combinations of list elements. O(n log n) – merge sort, quick sort

There is also Factorial Time O(log n!), but we shall not show an example here.


Time Complexity Chart

Below is the chart of the various Time Complexities – see differences from least to most complex.