I need help to verify my answer. Analyze the running time for the function

user_11995987 0
Viewed 91
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; 
}

My thinking:
1st loop runs n times. so running time is theta of N. 0(n) + 2nd loop inner loop runs. j times which j= 1+ 2 + 4 + 8. thats the sum of n(n+1) (2n+1)/6 ==> theta n^3

so Total Running time = 0(n)+ 0(n^3)

Please comment on my answer and let me know if my logic is correct or I am missing something. I am very new to programming.

algorithm
2 Answers

The first loop is O(n).

After running the first loop,

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

So, the second loop is

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

Total complexity is

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

The 1st loop is O(n), the 2nd is O(n) and the 3rd is 1+2+4+... = 2^n - 1. Therefore, the total is O(n) + O(n 2^n) = O(n 2^n).

user_142703260
Related