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

Solution: Nested Loop with Multiplication (Intermediate)

Explore how to analyze the time complexity of nested loops where the inner loop multiplies the index, leading to an O(n log n) runtime. Learn to break down each loop's iterations and combine them to accurately derive the Big O notation for intermediate algorithm complexity.

We'll cover the following...

Solution #

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

  • Outer Loop: 1+4+7+10+⋯+n=n31+4+7+10+\cdots+n = \frac{n}{3}

  • Inner Loop: 1+3+9+27+⋯+n=log3n1+3+9+27+\cdots+n = log_3 n ...

Statement Number of Executions
n = 10 1
sum = 0 1
pie = 3.14 1
for var in range(1,n,3): n3\frac{n}{3}
j=1 n3\frac{n}{3}