java之为什么 2 for 循环的时间复杂度不是 O(n*2^n)

此方法的时间复杂度为 O(2^n)根据我的教授。

我觉得这个方法的时间复杂度应该是O(n * 2^n)因为

外部 for 循环成本 O(n)
内部 for 循环成本 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; 
} 

请您参考如下方法:

考虑一下:

对于 i = 0 :j = 1 -> 2^0
对于 i = 1 :j = 2 -> 2^1
对于 i = 2 :j = 4 -> 2^2
对于 i = 3 :j = 8 -> 2^3....

对于 i = n-1 :j = 2^n-1
如果您添加所有这些:

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