Teaching Haryana (HPSC) Assistant Professor Mock Test 2025 Algorithms Algorithm Design Techniques Dynamic Programming
Consider the following code segment to find the nth Fibonacci number:
fib(n)
{
if(n==0) {return 0;}
if(n==1) {return 1;}
else {return(fib(n-1) + fib(n-2);}
}
The time complexity of the above code and time complexity of the same problem solved using dynamic programming are ______ and ____ respectively.
1
O(n2), O(n)
2
O(2n) , O(n)
3
O(2n) , O(n2)
4
O(nn) , O(2n)
5
Question Not Attempted