AI Features
Home
Courses
Data Structures for Coding Interviews in Python

Solution: Big O of Nested Loop with Multiplication

This review provides a detailed analysis of the different ways to solve the Big O of Nested Loop with Multiplication problem.

We'll cover the following...

Solution

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

Explanation

The answer is O(n)O(n). Have a look at the slides below for an in-depth explanation of the answer.

In the slides below, rtc abbreviates the running time complexity.

Time Complexity

The above slides give a detailed, step-by-step analysis of the code. Here, we provide a more summarized version.

The outer loop here runs log(n)log(n) ...