Time & Space Complexity

Question

Consider the following pseudo code written in C style:

bool fun(int arr[],int n,int X)
{
    if(X == 0) 
        return true;
    if(n == 0 && X !=0)
        return false;
    if(arr[n-1]*arr[n-1] > X)
        return fun(arr, n-1, X);
    return fun(arr,n-1,X) || fun(arr,n-1,X - arr[n-1]*arr[n-1]);
}

Which of the following is true about the above code:

(a) Time complexity of fun() is O(2n) and it requires O(n) extra space

(b) Time complexity of fun() is O(2n) and it requires O(n2) extra space

(c) Time complexity of fun() is O(n2) and it requires O(n) extra space

(d) Time complexity of fun() is O(n2) and it requires O(n2) extra space

Comments

Is option C is correct?

---

no the correct answer is A

Answer 1

See how many function calls are active in the stack. Here, function 'fun(n)' can give a call to fun(n-1), which inturn will call fun(n-2) and so on.. till n=0.

When n becomes 0, fun will start returning, ie, it starts popping out of the stack. So, at max, there are n to 0, functions in the stack. Hence space complexity is O(n).

Answer 2

Please refer

https://gateoverflow.in/37892/geek_mock_quetion_14