Big O Practice: Doubling Inner

def count_doublings(arr):
    n = len(arr)
    count = 0
    for i in range(n):
        j = 1
        while j < n:
            count += 1
            j *= 2
    return count

Variables

• n - length of the input array

Explanation

Looks quadratic at first glance - two nested loops - but the inner loop multiplies `j` by 2 each step, so it runs **O(log n)** times, not `n`. Outer × inner = **O(n log n)**. Space is **O(1)**.

More Big O practice problems · Today's daily problem