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

Solution: Big O of Nested Loop with Multiplication

Explore how to evaluate the time complexity of nested loops that feature multiplicative growth. This lesson helps you understand how to break down the loops' behavior, sum geometric series, and correctly determine the Big O notation as linear time O(n). You will gain the skills to analyze runtime complexity in scenarios where inner loops grow exponentially relative to the iterations of the outer loop.

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) ...

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) ...