Q. 1. Recursive Equations [25\%] Solve the following recurrence equations and give a $\theta$ bound in terms of $n$ for each of them. (1) $T(n)=T(n-2)+1; T(0)=0 ; n$ is even and Sn \geq 0 [5 %]$ (2) ST(n)=f(n-1)+2 n ; T 0 )=0 ; n \geq $. [5\%] (3) $T(n)=4 T\left(\frac{n}{2} ight)+1; T(1)=0 ; n \geq 1$ (You may assume thatt $n=2^{m}$ and $m$ is a natural number) [5\%] (4) $T(n)=4 T\left(\frac{n}{4} ight)+n ; T(1)=0$. (You may assume that $n=4"{m}$ where $m$ is a natural number) [5%) (5) $T(n)=\left\{\begin{array}{11}2 & n=3 TC\sqrt(3){n})+2 & n>3\end{array} ight. $. (You may assume that $n=3^{3^{m}}$ where $$ is a natural number) [5%] SP.50.315