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=n3 ...