我需要帮助来验证我的答案.分析函数的运行时间

Question

int func2(int n) { 
int i, j;
int sum;
arr = new int[n];
for (i = 0, j = 1; i < n; i++, j *= 2) {
arr[i] = j;
}

sum = 0;
for (i = 0; i < n; i++) {
for (j = 1; j <= arr[i]; j++) {
sum += (i + j);
}
}

delete []arr;
return sum; 
}

我的想法是：
第一个循环运行n次。所以运行时间是θ。0(N(+第二个环路内环运行。j乘以j＝1+2+4+8。这是n(n+1((2n+1(/6＝＝>θn^3

所以总运行时间=0(n(+0(n^3(

请评论我的答案，让我知道我的逻辑是否正确或我遗漏了什么。我对编程很陌生。

Answer 1

第一个循环是O(n(。

运行第一个循环后，

arr = [1, 2, 4, 8, ... , 2^(n-1)]

所以，第二个循环是

O(1+2+4+ ... +2^(n-1)) = O(2^n - 1) = O(2^n)

总复杂度为

O(n + 2^n) = O(2^n)

Answer 2

第一个循环是O(n(，第二个是O(n(，第三个是1+2+4+…=2^n-1。因此，总数为O(n(+O(n2^n(=O(n2^2(。