Why is the time complexity of 2 for loops not O(n*2^n)?

Question

The time complexity for this method is O(2^n) according to my prof.

I feel that the time complexity for this method should be O(n * 2^n) because

The outer for loop cost O(n)

The inner for loop cost O(2^n)

public static int loop(int n) {
    int j = 1;
    for (int i = 0; i < n; i++) {
        for (int k = j; k > 0; k--) {
            System.out.println("Hello world");
        }
        j *= 2;
    }
    return j;
}

Answer 1

Consider this:

For i = 0 : j = 1 -> 2^0

For i = 1 : j = 2 -> 2^1

For i = 2 : j = 4 -> 2^2

For i = 3 : j = 8 -> 2^3 ....

For i = n-1 : j = 2^n-1

If you add all of those :

2^0 + 2^1 + 2^2 +.....+2^(n-1) => order of 2^(n) -> 2^(n) - 1 to be precise

So the time complexity is O(2^n)

Answer 2

You are correct that the outer loop runs O(n) times. You are also correct that the maximum amount of time the inner loop takes to finish is O(2ⁿ). So it is not incorrect to say that the work done here is no more than O(n2ⁿ).

However, this bound isn’t tight, since this analysis assumes that the work done on each iteration of the inner loop is equal to the maximum work done by the inner loop across each iteration. Reasoning by analogy: if I have ten animals and the heaviest one is a 1,000kg elephant, I can correctly say that the animals collectively weigh at most 10,000kg by multiplying the number of animals by the maximum mass, but that might be a wild overestimate. I’d be better off just adding up the masses of each individual animal to see what I get.

In this case, the observation we need is that the ith time we go through that inner loop, we spend 2ⁱ iterations. That means that the total work done is roughly

2⁰ + 2¹ + ... + 2^n-1.

This is the sum of a geometric series and it works out to 2ⁿ - 1, hence the overall O(2 ⁿ) time bound. Going back to the animal example, if my animals are a 1kg squirrel, a 10kg tortoise, a 100kg human, and a 1,000kg elephant, almost the entirety of the mass is accounted for by the elephant because the masses grow so quickly. The formal expression for the sum of a geometric series makes that idea mathematically rigorous.