Algorithm Analysis | Part 2 - Time Complexity Analysis

If you're viewing this post for the first time, I highly recommend you to go through the Part 1 of What is Big O Notation And Why Every Programmer Must Know What It Is! series ...

As mentioned previously, Big O notation doesn't show the time an algorithm will consume to run successfully. Instead, it shows the number of operations it will perform. It tells you how fast an algorithm grows and lets you compare it with others.

Consider the below code, where an array is defined with 100 integers

oneToHundred = list(range(1, 101))

If we were to print a number from the above list, assuming that the acccess to any element in a list is always a constant access then, the TC of the following code is O(1)

oneToHundred = list(range(1, 101))

print(oneToHundred[0])  # constant time
print(oneToHundred[50]) # constant time
print(oneToHundred[99]) # constant time

If we were to print all the numbers from the above list, assuming that the acccess to any element in a list is always a constant access then, the TC of the following code is O(n)

oneToHundred = list(range(1, 101))

for i in range(len(oneToHundred)):   # loop from first to last element
    print(oneToHundred[i])           # constant time

The TC of the following code is also O(n)

oneToHundred = list(range(1, 101))

for i in range(len(oneToHundred)/2):   # loop from first to mid element
    print(oneToHundred[i])             # constant time

Next, let's explore the TC of the famous Binary Search Algorithm.

oneToHundred = list(range(1, 101))       # Sorted Array

def binary_search(inputList, elementToFind):
    low = mid = 0
    high = len(inputList) - 1

    while low <= high:
        mid = (high + low) // 2
        if inputList[mid] < elementToFind:   # If elementToFind is greater,
            low = mid + 1                    # ignore left half
        elif inputList[mid] > elementToFind: # If elementToFind is smaller,
            high = mid - 1                   # ignore right half
        else:
            return mid                       # elementToFind is present at mid
    return -1                            # If we reach here, then the element was not present


print(binary_search(oneToHundred, 10))

In the above code we see that a lower and the higher bounds are established, and we loop until the lower bound exceeds the higher bound at some point. Since this loop is different from the for loop which traditionally had a initial index and a range that we say earlier, you might think finding the TC of this algorithm is hard. But its not... why? because we already have the lower and upper bounds established and we know that initially high - low = n where n is the length of the input array. Furthermore, If we observe the code inside the loop we see that the logic branches in 3 ways, in the first 2 cases it seems we are reducing the bounds by half and in the 3rd case it's a simple return, which halts the function execution. The 3rd case obviously takes constant time since it executes ones in its lifetime.

Arguably, the first and the second conditions, when executed are reducing the bounds by half each time. The question is how many times must we divide our input in half until we get down to 1? Assume there are x such divisions.

# keep on reducing the bound by half until we go down to 1
n * 1/2 * 1/2 * 1/2 * 1/2 * .... = 1  

On simplification, we get n = 2^x, where x is the number of time we must divide to get down to 1. We don't know x yet but let's simplify further. But how do we get the x out of the exponent? Logarithms! (High School Math 😏)

Taking log₂ on both sides, we get log₂(n)=x. We have thus simplified for x, which means that the number of times we must divide n in half to get down to 1 is log₂(n). Hence our simplified TC is O(log(n)).

Time to celebrate 🎉🥳🎊, No Kiddin! This was definitely hard to digest if you are a beginner, but let it sink in. Once you understand it, you'll never forget it!

As a challenge, let's test to see if you really understood all the analysis stratergies we discussed up until now. Can you find the TC of the following code ?

oneToHundred = list(range(1, 1001))

low = 1
high = len(oneToHundred)

while low <= high:
    print(low)
    low *= 2

Big-O Refresher & Cheatsheet 🚀#

Big O notations and their performance comparisons against different sizes of the input data#

Data Structure Operations Complexity#

Array Sorting Algorithms Complexity#

In the next part we will understand how to analyse the Space Complexity for a given algorithm.