Data Structures for Coding Interviews in Python/

...

/

Solution: Nested Loop with Multiplication (Basic)

Solution: Nested Loop with Multiplication (Basic)

This review provides a detailed analysis of the different ways to solve the nested loop with multiplication problem.

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