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)log_3(n) times since var will first be equal to 11, then 33, then 9,⋯9,\cdots, until it is 3k3^k such that 3k≤n3^k \leq n. This means that the outer loop runs a total of log3(n)log_3(n) times. The inner loop, on the other hand, runs a total of log3(n)×n2log_3(n)\times\frac{n}{2}. So,

Statement
Number of Executions
n = 10 1
sum = 0 1
pie = 3.14 1
var = 1 1
while var < n: log3(n)log_3(n)
...