Time Complexity in Recursion

#1

Sir said not to use exponential time complexity . Then what’s the other approach to solve this program ?

#2

Hey @vanshikasharma1645
We know fibo[n]=fibo[n-1]+fibo[n-2]
use array instead of size n
Initially set fibo[0]=0 and fibo[1] as 1
and then run a loop
for(int i=2;i<=n;i++) fibo[n]=fibo[n-1]+fibo[n-2]

#3

This is O(n) space & time