Composing complexity classes

Normally, we need to find the total running time of complex operations and algorithms. It turns out that we can combine the complexity classes of simple operations to find the complexity class of more complex, combined operations. The goal is to analyze the combined statements in a function or method to understand the total time complexity of executing several operations. The simplest way to combine two complexity classes is to add them. This occurs when we have two sequential operations. For example, consider the two operations of inserting an element into a list and then sorting that list. Assuming that inserting an item occurs in O(n) time, and sorting in O(nlogn) time, then we can write the total time complexity as O(n + nlogn); that is, we bring the two functions inside the O(…), as per Big O computation. Considering only the highest-order term, the final worst-case complexity becomes O(nlogn).

If we repeat an operation, for example in a while loop, then we multiply the complexity class by the number of times the operation is carried out. If an operation with time complexity O(f(n)) is repeated O(n) times, then we multiply the two complexities: O(f(n) * O(n)) = O(nf(n)). For example, suppose the function f(n) has a time complexity of O(n²) and it is executed n times in a for loop, as follows:

for i in range(n):
        f(...)

The time complexity of the above code then becomes:

O(n²) x O(n) = O(n x n²) = O(n³)

Here, we are multiplying the time complexity of the inner function by the number of times this function executes. The runtime of a loop is at most the runtime of the statements inside the loop multiplied by the number of iterations. A single nested loop, that is, one loop nested inside another loop, will run n² times, such as in the following example:

for i in range(n):
    for j in range(n)
        #statements

If each execution of the statements takes constant time, c, i.e. O(1), executed n x n times, we can express the running time as follows:

c x n x n = c x n² = O(n²)

For consecutive statements within nested loops, we add the time complexities of each statement and multiply by the number of times the statement is executed—as in the following code, for example:

def fun(n):
   for i in range(n):  #executes n times
      print(i)     #c1
   for i in range(n): 
      for j in range(n):
         print(j)  #c2

This can be written as: c¹n + c² *n² = O(n²).

We can define (base 2) logarithmic complexity, reducing the size of the problem by half, in constant time. For example, consider the following snippet of code:

i = 1
while i <= n:
    i = i*2
    print(i)

Notice that i is doubling in each iteration. If we run this code with n = 10, we see that it prints out four numbers: 2, 4, 8, and 16. If we double n, we see it prints out five numbers. With each subsequent doubling of n, the number of iterations is only increased by 1. If we assume that the loop has k iterations, then the value of n will be 2ⁿ. We can write this as follows:

From this, the worst-case runtime complexity of the above code is equal to O(log(n)).

In this section, we have seen examples to compute the running time complexity of different functions. In the next section, we will take examples to understand how to compute the running time complexity of an algorithm.