GATE CSE
First time here? Checkout the FAQ!
x
0 votes
158 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 in Algorithms by Active (1.5k points)   | 158 views

1 Answer

+5 votes
Best answer
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.7k points)  
selected by


Top Users Jul 2017
  1. Bikram

    5368 Points

  2. manu00x

    3092 Points

  3. Arjun

    1924 Points

  4. joshi_nitish

    1898 Points

  5. Debashish Deka

    1874 Points

  6. pawan kumarln

    1454 Points

  7. Tesla!

    1390 Points

  8. Hemant Parihar

    1314 Points

  9. Shubhanshu

    1136 Points

  10. Arnab Bhadra

    1124 Points


24,141 questions
31,143 answers
70,892 comments
29,467 users