Trying to calculate time and storage complexity for a function (C)

Question

edit: I figured out how to properly calculate the time complexity but still can't figure out the storage complexity.

edit:figured everything out.

I tried solving a complexity question and failed.

The answer should be : time complexity - n(m+n), storage complexity - m+n.

Please help me understand where I am wrong and suggest a way to understand/solve these types of questions better.

Here is the function:

void f(int n, int m){
     if (n <= 1) {
         int *arr=malloc(m*sizeof(int));
         for (int i=0; i<m; i++) arr[i] = 0;
         free(arr);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

From what I see "free(arr)" frees the memory that malloc allocates, which makes malloc irelavent in terms of time complexity. edit: someone explained me that even though we use 'free' the malloc is still taken into consideration (space cpmlexity wise).

I see that the first function call makes the function call itself n times and when that happens m is incramented by 1 - n times, so the time complexity for the first func call is n(m+1) and the storage complexity n- since there are n calls to the function in recursion. edit: figured it out eventually.

The second function call calls the function log(n) times and m is incremented log(n) times which makes the time complexity for this call : log(n)(m+1). Storage complexity:log(n).

So total time complexity is n(m+1), total storage complexity is n.

Answer 1

It is actually a tricky question! The second function call f(n%2, m+1) is just calling the recursive f once because it calculates the reminder of n to 2 which can be either 1 or 0! and in both cases the f function is returned without any further recursive call. So it is not log n.

The function f is called once in f(n-1, m+1) n times and just right after that in f(n%2, m+1), it will be called again once more time. It is then O(2n) if only considering n factor.

Now considering the m factor, we will notice that the loop inside the if is repeating m times and m is increasing by one at each recursive call (and actually decreasing when it returns back from the recursive call!) so it would be the sum of (m+n ... m+1) which is O(mn+n(n+1)/2). It after the simplification.

Therefore considering both factors the time complexity is O(2n+mn+n(n+1)/2) which is actually after simplifying equivalent to O(nm+n^2).

Regarding the storage complexity: The m is incremented for the first call (m+1) which will continue for n times but the second call is not continued, so the storage complexity will be O(n+m).

Answer 2

void f(int n, int m){
     if (n <= 1) {
         int *arr=malloc(m*sizeof(int));
         for (int i=0; i<m; i++) arr[i] = 0;
         free(arr);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

Let's refactor it:

void f1(int m) {
    int *arr = malloc(m*sizeof(int));
    for (int i = 0; i < m; i++) {
        arr[i] = 0;
    }
    free(arr);
}

void f(int n, int m){
     if (n <= 1) {
         f1(m);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

So for f1 it's quite simple, - space complexity is sizeof(int) * m - we need to allocate that much - and time complexity is just m - we are looping through all the m elements in the array arr.

The n%2 can only be 1 or 0, so we can substitute the f(n%2, m+1); for f1(m+1).

void f(int n, int m){

     if (n <= 1) {
         f1(m); // (1)
         return;
     }

     f(n-1, m+1); // (2)

     f1(m + 1); // (3)
}

Now. If n > 1 then we call f(n-1, ... until n <= 1. For each n > 1 we call f1(m + 1) in the reverse chronological order (because it's after the recursive call). When we get to n <= 1 then f1(m) is called with m = m(initial) + n(initial) - 1 times. Och, maybe an example for example for n=5, then:

• initial call to f(5, m) so n=5
• n=5, so we call f(4, m+1) // (2)
• n=4, so we call f(3, m+2) // (2)
• n=3, so we call f(2, m+3) // (2)
• n=2, so we call f(1, m+4) // (2)
• n=1, so we call f1(m+4) and return // (1)
• n=2, after (2), so we call f1(m+4) // (3)
• n=3, after (2), so we call f1(m+3) // (3)
• n=4, after (2), so we call f1(m+2) // (3)
• n=5, after (2), so we call f1(m+1) // (3)

We can see that f1(m+4) is called twice, and that we are calling f1(m + i) in reverse order from i=1 to i=4.

We can "unfold" the function:

void f(int n, int m){
     f1(m + n - 1);
     for (int i = n - 1; i > 0; --i) {
         f1(m + i);
     }
}

As both m and n approach infinity the +1 or -1 mean nothing.

The space complexity is the space complexity of f1(max(m + i, m + n - 1)), because f1 frees the memory each time. So it's (m + n - 1) * sizeof(int) which is (m + n) * sizeof(int), which is m + n.

The time complexity is dependent on how many times we call f1 function. We see that we call:

f1(m + n - 1)
f1(m + n - 1)
f1(m + n - 2)
...
f1(m + 2)
f1(m + 1)

So the time complexity is

(m + n - 1) + ((m + n - 1) + (m + n - 2) + ... + (m + 1))
(m + n - 1) + (n - 1) * m + ((n - 1) + (n - 2) + ... 1)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
// the `*2`, `/2`, `+1` and `-1` mean nothing close to infinity
 m + n      + n       * m + n        *  n
m + n + m * n + n * n
m * (n + 1) + n * (n + 1)
(m + n) * (n + 1)
(m + n) * n