in Algorithms retagged by
604 views
0 votes
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

in Algorithms retagged by
by
604 views

2 Comments

Is option C is correct?
0
0
no the correct answer is A
1
1

2 Answers

6 votes
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).
0 votes
0 votes
by

Related questions

1 vote
1 vote
1 answer
1