What's the worst space complexity of a loop which create an arrayat each iteration-CodePudding

I am struggling to find a proper definition of worst space complexity whether it is the sum of the total amount of the algorithm used or if it is only the space consumed by the algorithm at a critical time, the worst one.

As an example:

void myFunc(n) {
  for(int j = 0; j < n ;   j) {
     int* myTab = malloc(n*sizeof(int));
     for(int i = 0; i < n;   i) {
        myTab[i] = 1;
     }
      free(myTab);
   }
}

For the first definition it is roughly O(N²) and for the second one O(N).

CodePudding user response：

It would be O(n). You are explicitly freeing up the memory after the assignment is done. I agree the inner workings of the malloc would be useful but assuming a normal implementation which doesn't use memory enough to change the space complexity ( For tracking O(n) memory allocation it keeps O(n^2) amounts of metadata - just a weird example).

An interesting point, to clear up your idea. If you comment out this free(..) line, then the space complexity would be O(n^2). This is what is known as memory leakage.