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

Solution: Nested Loop with Multiplication (Advanced)

Explore how to evaluate time complexity for a nested loop where the inner loop's index doubles each iteration. Understand the derivation of the O(n log n) time complexity using properties of logarithms and factorials. This lesson helps you apply complexity measures to algorithm analysis in Python.

We'll cover the following...

Solution

Python 3.5
n = 10  # can be anything
sum = 0
pie = 3.14
for i in range(n):
    j = 1
    while j < i:
        sum += 1
        j *= 2
    print(sum)

In the main function, the outer loop is O(n)O(n) ...