$\mathbf{Q} \# 3$ : (a) Find an asymptotic upper bound for the recurrence $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n}- \mathrm{a})+\mathrm{T}(\mathrm{a})+\mathrm{n}$ where $\mathrm{a}>=1$ is constant, by using recursion iteration to generate a guess. For base case we assume that $\mathrm{T}(\mathrm{n}) \varepsilon$ $\Theta(1)$ for $\mathrm{n} \leq \mathrm{a}$, i.e. that $\mathrm{T}(1), \mathrm{T} (2), \ldots \ldots \mathrm{T}$ (a) are all constants. (b) Complete the substitution method by proving that the guess generated above is indeed an asymptotic upper bound for the recurrence cs.vs. 1231