Is option C is correct?

Dark Mode

604 views

0 votes

**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

6 votes

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

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