1

In one of the previous intro to cs exams there was a question: calculate the space and time complexity of the function f1 as a function of n, assume that the time complexity of malloc(n) is O(1) and its space complexity is O(n).

int f1(int n) {
    if(n < 3)
        return 1;

    int* arr = (int*) malloc(sizeof(int) * n);
    f1(f1(n – 3));
    free(arr);

    return n;
}

The official solution is: time complexity: O(2^(n/3)), space complexity: O(n^2)

I tried to solve it but i didn't know how until i saw a note in my notebook that said: since the function returns n then we can treat f(f(n-3)) as f(n-3)+f(n-3) or as 2f(n-3). In this case the question becomes very similar to this one: Space complexity of recursive function

I tried solving it this way and i got the correct answer.

For the time complexity:

T(n)=2T(n-3)+1 , T(0)=1

T(n-3)=2T(n-3*2)+1

T(n)=2*2T(n-3*2)+2+1

T(n-3*2)=2T(n-3*3)+1

T(n)=2*2*2T(n-3*3)+2*2+2+1

...

T(n)=(2^k)T(n-3*k)+2^(k-1)+...+2^2+2+1

n-3*k=0

k=n/3

===> 2^(n/3)+...+2^2+2+1=2^(n/3)[1+(1/2)+(1/2^2)+...]=2^(n/3)*constant

Thus I got O(2^(n/3))

For the space complexity: the tree depth is n/3 and each time we do malloc so we get (n/3)^2 thus O(n^2).

My question:

  • why can we treat f1(f1(n – 3)) as f1(n-3)+f1(n-3) or as 2f1(n-3)?
  • if the function didn't return n but changed it, for example: return n/3 instead of return n, then how do we solve it? do we treat it as 2f1((n-3)/3)?
  • if we can't always treat f1(f1(n – 3)) as f1(n-3)+f1(n-3) or as 2f1(n-3) then how do we draw the recursion tree and how do we write and solve it using the induction method T(n)?
Titan3
  • 106
  • 10

1 Answers1

1

  • Why can we treat f1(f1(n – 3)) as f1(n-3)+f1(n-3) or as 2f1(n-3)?

    Because i) the nested f1 is evaluated first, and its return value is used to call the outer f1; so these nested calls are equivalent to:

    int result = f1(n - 3);
f1(result);

    ... and ii) the return value of f1 is just its argument (except for the base case, but it doesn't matter asymptotically), so the above is further equivalent to:

    f1(n - 3);
f1(n - 3); // result = n - 3

  • If the function didn't return n but changed it, for example: return n/3 instead of return n, then how do we solve it? do we treat it as 2f1((n-3)/3)?

    Only the outer call is affected. Again, using the equivalent expression from before:

    f1(n - 3); // = (n - 3) / 3
f1((n - 3) / 3);

    i.e. just f1(n - 3) + f1((n - 3) / 3) for your example.

  • If we can't always treat f1(f1(n – 3)) as f1(n-3)+f1(n-3) or as 2f1(n-3) then how do we draw the recursion tree and how do we write and solve it using the induction method T(n)?

    You can always separate them into two separate calls as above, and again remember that only the second call is affected by the return result. If this is different to n - 3 then you would need a recursion tree instead of simple expansion. Depends on the specific problem, needless to say.

meowgoesthedog
  • 14,670
  • 4
  • 27
  • 40
  • Okay so when we reach that line of code the inner ("nested") function will be evaluated first, the inner function will start "going down the recursion", meaning it will call f1(n-3), and then when we reach that line of code again the inner function will be evaluated first again calling f1(n-3*2) and so on until we reach the base case, then it will start returning the values and the last value it returns is what it started with meaning n-3, and then the outer function will start "going down the recursion" with that value. Is my intuition correct? – Titan3 Sep 26 '18 at 23:09
  • @TitanEilabouni Not quite - you have to think of the recursion path as a binary tree - each call divides into two calls (the inner and outer). That's why writing them separately as in the answer above helps with the thought process. – meowgoesthedog Sep 27 '18 at 08:18