I've just started learning time and space complexity and I'm having trouble in calculating it for this program.

void f(int n){
    int a[4] = {1, 1, 1, 1};
    for(int k = 0; k < n; k  ){
        a[k % 4] *=3;
    }
    int** ptr = (int **)malloc(a[0]*sizeof(int*));
    for (int j = 0; j < a[0]; j  ) {
        *(ptr j) = (int*)malloc(j*sizeof(int));
        for(int k = 0; k < j; k  ){
            printf("*");
        }
    }
}

I've tried to use the methods that I learned but im not sure how to use them correctly.

Can somebody explain me how to find the complexity of this example?
Thanks in advance for any help!

CodePudding user response：

The first loop iterates n times. The body is a constant-time equation, so the loop is O(n).

Each time the loop cycles through the a array, it multiplies the elements by 3, so the result is that the value of each element is asymptotically proportional to 3ⁿ.

The only element that matters for the second loop is a[0]. So the outer loop iterates O(3ⁿ) times.

The inner loop iterates j times, where j goes from 0 to 3ⁿ-1. The formula for the sum of the sequence 1, 2, ... x is x * (x 1) / 2, which is O(x²).

When you combine these, the resulting complexity is O((3ⁿ)²).

The space complexity is the same, since the total size of the arrays allocated in the loop are the same as the number of iterations of the inner loop.