Algorithm Analysis | Part 1 - The Time Complexity

Here is a question to all the programmers out there. How do we express the runtime of a program? Do we measure the runtime directly? Do processor speed and the load on it matter? Do we express the runtime in seconds? If you're curious about the answers to all these questions, then I urge you to read along. The journey ahead is an interesting one!

Let us assume that we relied on the time that is taken for the execution of an algorithm to measure its efficiency. Below is a python snippet that prints the numbers 1 to n onto the console, where n is any postive integer.

import time

def print_1_to_n(n):
    for i in range(n):
        print(i)

start = time.time()
print_1_to_n(10)
end = time.time()

print("Total Execution Time: ",round((end - start)*1000, 4),"ms")

Try to execute the above code locally or on an online repl.it instance. Run it several times. Take a closer look at the logged Total Execution Time every time you run it. It is not the same, this can be due to various reasons pertaining to the load on the processor and the amount of context switching happening internally, and various physical factors like heat and temperature that directly affects the processor speeds. Ideally, the result will be different of different machines and faster the pocessor, faster is the execution.

Hence the time taken for the execution of an algorithm to measure its efficiency is not a reliable metric! We need a universal language where the measurement is independent of external factors like processor speeds or the amount of RAM used.

What if we could express the runtime in terms of how quickly it grows relative to the input, as the input gets arbitrarily large. This representation of runtime relative to the growth of the given input is known as Big O notation. Big O notation is all about how we compare the efficiency of different approaches or solutions to a problem.

Now that we know what Big-O notation is, How do we express it? Since we are not relying on the time taken which would have been in seconds and we are measuring how quickly our runtime grows. We need to express our speed in terms of...something else. Therefore, Big O notation uses the size of the input, which we call O(n) which means the runtime grows "on the order of the size of the input". Likewise, O(n^2) means the runtime grows"on the order of the square of the size of the input".

Analysis With Examples#

def print_first_element(list):
    print(list[0])

This function which prints the first element in the input list runs in O(1) time (a.k.a "constant time") relative to its input. The input list could be 1 element or 1000 elements, but this function would still require just one step.

def print_all_elements(list):
    for element in list:
        print(element)

This function which prints all the elements in the list runs in O(n) time (a.k.a "linear time"), where n is the number of elements in the list. If the list has 10 elements, we have to print 10 times. If it has 1000 elements, we have to print 1000 times. In general, if we have n elements we have to print n times.

def print_all_possible_ordered_pairs(list):
    for first in list:
        for second in list:
            print(first, second)

Here we're nesting two loops. If our list has n elements, our outer loop runs n times and our inner loop runs n times for each iteration of the outer loop, giving us n^2 total steps. Thus this function runs in O(n^2) time (a.k.a "quadratic time"). If the list has 10 elements, we have to print 100 times. If it has 1000 elements, we have to print 1000000 times. In general, if we have n elements we have to print n^2 times.

There are times where n could be the actual input, or the size of the input. Both of these functions have O(n) runtime, even though one takes an integer as its input and the other takes a list of n elements.

def print_1_to_n(n):
    for i in range(n):
        print(i)


def print_all_items(list):
    for element in list:
        print(element)

In Big O analysis, we primarily care about the stuff that grows fastest as the input grows, because everything else quickly diminishes as n grows larger. Since the dominant terms becomes more and more significant we drop the less significant terms and focus on the dominant terms. For example

def print_all_numbers_then_all_pair_sums(numbers):
    print("these are the numbers:")
    for number in numbers:
        print(number)

    print("and these are their sums:")
    for first_number in numbers:
        for second_number in numbers:
            print(first_number + second_number)

Here our runtime is O(n + n^2), which we just call O(n^2). So, even if it was O((n^2)/2 + 100n), it would still be O(n^2). Similarly:

• O(n^3 +50n^2 +10000) is O(n^3)
• O((n+30)∗(n+5)) is O(n^2)

Big O notations and its terms#

Given an input how many steps does an algorithm take to run successfully ? Does it take a constant step, linear step ... or an infinite step ? Notation's complexity mentioned below increases from top to bottom

• O(1): Constant Time
• O(log(n)): Logarithmic Time
• O(n): Linear Time
• O(nlog(n)): Linearithmic Time
• O(n^2): Quadratic Time
• O(n^c): Polynomial Time
• O(n!): Factorial Time
• O(∞): Infinite Time

In the next part let's dive deep into analysis of Time Complexity of a given algorithm and understand some of the pitfalls to avoid.