CODEWITHSUNDEEP
recursiontime-complexitybig-ospace-complexity
Titan3
Titan3

Reputation: 106

Time and space complexity of a "nested" recursive function

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:

Upvotes: 1

Views: 1316

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

  • 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.

Upvotes: 1

Related Questions