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