$(3)[20$ pts$.]$ Given this method:

METHOD T$1$:

public int T$1($ int n $)\{$

if $($n $<1)\{$

return $0$;

$\}//$ if

else $\{$

return $($n $+$ T$1($n$-1))$;

$\}//$ else

$\}//$ T$1$

$($a$)$ Set up a recurrence relation for the running time of the method T$1$ as a function of n$.$ Solve your recurrence relation to specify theta bound of math$1.$

METHOD T$2$:

public int T$2($int n$)\{$

if $($n $<1)\{$

return $0$;

$\}//$ if

else $\{$

return T$1($n$)+$ T$2($n$/2)$ n$/2$;

$\}//$ else

$\}//$ T$2$

$($b$)$ Now set up a recurrence relation for the running time of the method T$2$ as a function of n$.$ Solve your recurrence relation to specify theta bound of math $2.$

HINT: When doing this, the call to T$1$ can be replaced by the equation that you found when solving the recurrence relation for T$1$ in part a$).(3)[20$ pts$.]$ Given this method:

METHOD T$1$:

public int T$1($ int n $)\{$

if $($n $<1)\{$

return $0$;

$\}//$ if

else $\{$

return $($n $+$ T$1($n$-1))$;

$\}//$ else

$\}//$ T$1$

$($a$)$ Set up a recurrence relation for the running time of the method T$1$ as a function of n$.$ Solve your recurrence relation to specify theta bound of math$1.$

METHOD T$2$:

public int T$2($int n$)\{$

if $($n $<1)\{$

return $0$;

$\}//$ if

else $\{$

return T$1($n$)+$ T$2($n$/2)$ n$/2$;

$\}//$ else

$\}//$ T$2$

$($b$)$ Now set up a recurrence relation for the running time of the method T$2$ as a function of n$.$ Solve your recurrence relation to specify theta bound of math $2.$

HINT: When doing this, the call to T$1$ can be replaced by the equation that you found when solving the recurrence relation for T$1$ in part a$).$