a$.(10$ pts$)$ Prove that if T$($n$)=8$n$2+2$n $+15,$ then T$($n$)=$ O$($n$2).$ Hint: You need to find two

positive constant values c and n$0$ such that T$($n$)<=$ cn$2$ for all n $>=$ n$0.$

b$.(10$ pts$)$ Suppose the running time of an algorithm is $7$n$2+22$m$2+4$nm $+10$m $+200,$

where n and m are positive integers such that n $>=$ m$.$ Prove that this algorithm is O$($n$2).$

c$.(20$ pts$)$ Give an analysis of the running time $($Big$-$Oh notation$)$ for the following

algorithms:

Firstly calculate T$($n$)$ and then find a tight upper bound $($Big$-$Oh$)$ for each algorithm. You do

not need to provide a proof.

sum $=0$;

i $=0$;

while$($i $<$ n$)\{$

sum$+=$i;

i$+=3$;

$\}$

while$($i $>0)\{$

sum$-=$i;

i$-=2$;

$\}$

while$($i $<$ sqrt$($n$)*2)\{$

sum$+=$i;

i$++$;

$\}$

i $=3*$n;

while$($i $>0)\{$

sum$-=$i;

i$--$;

$\}$

print$($sum$)$;

sum $=0$;

i $=0$;

while $($i $<$ n$)\{$

j $=1$;

while $($j $<=$ n$)\{$

sum $+=($i $+$ j$)$;

j$++$;

$\}$

i$*=2$;

$\}$

i $=0$;

while $($i $<10)\{$

j $=1$;

while $($j $<=$ n$)\{$

sum $-=($i $+$ j$)$;

j$+=2$;

$\}$

i$++$;

$\}$

i $=0$;

while $($i $<100000)\{$

sum $+=$ i;

i$++$;

$\}$

print$($sum$)$;