Problem $3.(35\%)$ Consider the following dummy recursive function: $1$For ESTR students, please feel free to use the generating function method if you feel more comfortable with the latter. $1$ Homework $32$ func$1($n$)$ for i $=1,...,$n: y $=$ i$*$i end for if n $==1$: return $0$ elseif n $==2$: return $1$ else: return func$1($n $1)+$ func$1($n $2)$ end if We define T$($n$)$ as the number of multiplication steps involved, i$.$e$.,$ the computation complexity, when running func$1($n$)$ with the input n$,$ where n in N$.$ Note that calculating i$*$i involves one multiplications. For example, we observe that T$(1)=1$ and T$(2)=2$ since respectively $1$ and $2$ multiplications are involved with the for$-$loop, before the function terminates. $($a$)(25\%,$ can be challenging$)$ Write down an inhomogeneous linear recursion for T$($n$).$ Solve the recursion. Remark: Notice that T$(1)=1,$ T$(2)=2$ as mentioned above. Try substituting different numbers of n as the input to the function and count the number of multiplications needed. $($b$)(5\%)$ Another function func$2($n$)$ has the complexity, H$($n$),$ governed by the recursion: for some a $2,$ H$($n$)=$ aH$($n $1),$ n $2,$ H$(1)=1.$ Solve the above recursion for H$($n$).($c$)(5\%)$ Using the results from $($a$),($b$).$

Which of the two functions is more efficient asymptotically, func$1($n$)$ or func$2($n$)?$ Justify your answer. In other words, determine if T$($n$)=$ o$($H$($