Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Python

Solution: Nested Loop with Multiplication (Advanced)

Explore how to evaluate time complexity for a nested loop where the inner loop's index doubles each iteration. Understand the derivation of the O(n log n) time complexity using properties of logarithms and factorials. This lesson helps you apply complexity measures to algorithm analysis in Python.

We'll cover the following...

Solution #

Python 3.5
n = 10  # can be anything
sum = 0
pie = 3.14
for i in range(n):
    j = 1
    while j < i:
        sum += 1
        j *= 2
    print(sum)

In the main function, the outer loop is O(n)O(n) as it iterates over n. The inner while loop iterates over i which is always less than n and j is doubled each time, therefore we can say that it is O(log2(n))O(log_2(n)). Thus, the total time complexity of the program given above becomes:

O(nlog2(n))O(nlog_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j which is less than i and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(i))O(log_2(\text{i})). But, the value of i at each iteration, of the outer loop, is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log2(i)⇒∑i=1nlog2(i)n \times log_2(i) \Rightarrow\sum_{i=1}^{n} log_2 (i) ...