Show that, if we use naive recursion, it takes exponential time $(\backslash$Omega $($an$)$ for some a $>1.)$ time to$$compute the n$-$th Fibonacci number Fn$.$ For simplicity, assume that adding any two numbers, regardless$$of the their size, takes one unit of time. $($Hint: write out the recurrence for T$($n$),$ the cost of$$computing the n$-$th Fibonacci number, and use induction. What happens if you try to prove a $\backslash$Omega $(2$n$)$bound$?$ Try a value smaller than $2$ instead.$)2.$ Describe an algorithm that reuses Fibonacci numbers that you have already calculated in order to$$output the first n Fibonacci numbers much faster $($e$.$g$.,$ in polynomial time rather than the naive$$exponential time algorithm$).3.$ How long does your algorithm take? State a $\backslash$Theta expression for the asymptotic run time of your algorithm.$$Again assume that adding any two numbers only takes one unit of time.