Simplify and express your answer as $\backslash$Theta $($n$\backslash$alpha $)$ or $\backslash$Theta $($n$\backslash$alpha log$2($n$))$ wherever

possible.

$$ Justify your answer. $($Show your work.$)$

$$ Be sure to justify both LOWER and UPPER bounds.

$$ WRITE YOUR ANSWERS ON A SEPARATE SHEET$/$FILE OR USE

AN ELECTRONIC DEVICE TO CREATE SPACE FOR YOUR AN$-$

SWER BELOW THE HOMEWORK QUESTIONS.

DO NOT SUBMIT A MARKED UP QUESTION SHEET WITH THE

ANSWERS IN THE MARGINS TO THE RIGHT OF THE QUESTIONS.

The grader will only grade a subset of these problems.

$1.$

func$1($n$)$

$1$ s $0$;

$2$ for i $$ n to n$3$ do

$3$ for j $26$ to $$i log$6($i$)$ do

$4$ s $$ s $+$ i $$ j;

$5$ end

$6$ end

$7$ return $($s$)$;

$2.$

func$2($n$)$

$1$ s $0$;

$2$ for i $38$ to n$3$ do

$3$ j $$ i$2$;

$4$ while $($j $>=6)$ do

$5$ s $$ s $+$ i $$ j $+$ k;

$6$ j $$j$/8$ ; $/*$ Note: Division $*/$

$7$ end

$8$ end

$9$ return $($s$)$;

$3.$

func$3($n$)$

$1$ s $0$;

$2$ for i $1$ to $$n$$ do

$3$ for j $1$ to i$3$ do

$4$ for k $$ j to i$3$ do

$5$ s $$ s $+$ i $$ j $+$ k;

$6$ end

$7$ end

$8$ end

$9$ return $($s$)$;

$1$