Recursionhard
0:00.0

Consider the recurrence T(n)=T(n1)+T(n2)T(n) = T(n-1) + T(n-2) with T(1)=1,T(2)=1T(1)=1, T(2)=1. If we implement this using memoization (top-down dynamic programming), what is the time complexity in terms of nn?