Find the order of growth of the following sums. Use the $\backslash$Theta $($notation with the

simplest function g$($n$)$ possible.$(5$ points$)$ Write an algorithm variation of sequential search that scans a list to return the number of

occurrences of a given search key in the list. Does its efficiency differ from the efficiency of classic

sequential search?

$(5$ points$)$ Suggest how any sorting algorithm can be augmented in a way to make the best$-$case

count of its key comparisons equal to just $n-1(n$ is a list's size, of course$).$ Do you think it would

be a worthwhile addition to any sorting algorithm?

$(5$ points$)$ For each of the following pairs of functions, indicate whether the first function of each of

the following pairs has a lower, same, or higher order of growth $($to within a constant multiple$)$

than the second function. Use $(\{$::${)}_1==$

a$.n(n+1),2000n^2$

b$.n^2,n^3$

c$.logn,lnn$

d$.(n-1)!,2^n$

$(5$ points$)$ Compute the following sums.

a$.1+3+5+7+$dots$+999$

b$.{\displaystyle \underset{i=1}{\overset{n+1}{}}}i$

c$.{\displaystyle \underset{i=0}{\overset{n-1}{}}}i(i+1)$

d$.{\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \underset{j=1}{\overset{n}{}}}ij$

$(5$ points$)$ Find the order of growth of the following sums. Use the $(g(n))$ notation with the

simplest function $g(n)$ possible.

a$.{\displaystyle \underset{t=0}{\overset{n-1}{}}}(i^2+1{)}^2$

b$.{\displaystyle \underset{t=2}{\overset{n-1}{}}}log{t}^2$

c$.{\displaystyle \underset{i=1}{\overset{n}{}}}(i+1)2^{i-1}$

d$.{\displaystyle \underset{t=0}{\overset{n-1}{}}}{\displaystyle \underset{j=0}{\overset{i-1}{}}}(i+j)$