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

Solution: Nested Loop with Multiplication (Basic)

Understand how to evaluate time complexity for nested loops involving multiplication in Python. This lesson helps you calculate logarithmic and linear execution counts leading to the Big O notation O(n log n).

We'll cover the following...

Solution

Python 3.5
n = 10  # n can be anything, this is just an example
sum = 0
pie = 3.14
var = 1
while var < n:
    print(pie)
    for j in range(1, n, 2):
        sum += 1
    var *= 3
print(sum)

Time Complexity

The outer loop in this problem, i.e., everything under line 5, while var < n runs log3(n) ...