What is the space complexity of the following recursive implementation to find the nth fibonacci number?
Posted: Wed Jul 13, 2022 6:16 pm
int fibo(int n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}
a) O(1)
b) O(2*n)
c) O(n2)
d) O(2n)
{
if(n == 1)
return 0;
else if(n == 2)
return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
int n = 5;
int ans = fibo(n);
printf("%d",ans);
return 0;
}
a) O(1)
b) O(2*n)
c) O(n2)
d) O(2n)