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

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 次。所以运行时间是 N 的 theta。0(n) +第二循环内循环运行。 j 乘以 j= 1+ 2 + 4 + 8。这就是 n(n+1) (2n+1)/6 ==> theta 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)