About the time complexity of top down dp

#1

how is the time to build up the ans of top down dp of the O(N)?

#2

Hey @Senjuti256
In fibonacci
we start from Fibo(n) and call Fibo(n-1) and Fibo(n-2)
So see here max n states are there i.e Fibo(n) …Fibo(n-1) …Fibo(n-1) …to …Fibo(1)
And since we return if already dp[i] exist hence that means recursion is running for n times only because of n states
Hence Time complexity is O(n)