iven these two methods:

METHOD math$1$:

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

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

CS$557$D: Algorithms $($Instructor: Dr$.$ Riabov$)$ Final Exam Fall $2024$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$2$

return $1$;

$\}//$ if

else $\{$

return $($ n $*2)+$ math$1($ n$-1)$;

$\}//$ else

$\}//$ math$1$

METHOD math$2$:

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

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

return $1$;

$\}//$ if

else $\{$

return n $+$ math$1($ n $)*$ math$2($ n$/2)$;

$\}//$ else

$\}//$ math$2$

$($a$)$ Set up a recurrence relation for the running time of the method math$1$ as a function of n$.$

Solve your recurrence relation to specify THETA bound of math$1.$

$($b$)$ Now set up a recurrence relation for the running time of the method math$2$ as a function

of n$.$ Solve your recurrence relation to specify the Big$-$O bound of math$2.$

HINT: When doing this, the call to math$1$ can be replaced by the equation that you found

when solving the recurrence relation for math$1$ in part $($a$))$