216 views
QUESTION 14 : Consider the below 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);
// Here "|| "indicates logical or
return fun(arr, n–1, X) || fun(arr, n–1, X – arrr[n–1]*arr[n–1]);
}

Which of the following is true about 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
Correct – A

How to calculate space complexity?

asked | 216 views

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).
answered by Loyal (3.8k points)
selected

1