Какова будет сложность времени для цикла, работающего до 2 для питания n?

Question

Какова будет временная сложность цикла от 2 до n?См. Ниже фрагмент кода.

int[] arr={1,2,3,4};
for(int i=0;i<arr.length;i++){
    for(int j=0;j<Math.pow(2,i);j++){
        System.out.println(j);
    }
}

Answer 1

Если у вас есть n элементов в массиве, вы выполните

2^0 = 1 computation in first loop
2^1 = 2 computation in second loop
2^2 = 4 computation in third loop
...
2^(n-1) = 2^(n-1) computation in n-th loop

Суммируя все это, вы получите 2^0 + 2^1 + 2^2 + ... + 2^(n-1) = 2^n-1 из формулы для суммы геометрических рядов.Таким образом, ваше время сложность составляет O(2^n)