Compute the following sums.

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

b$.2+4+8+16+$cdots$+1024$

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

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

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

f$.{\displaystyle \underset{j=1}{\overset{n}{}}}{3}^{j+1}$

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

h$.{\displaystyle \underset{i=1}{\overset{n}{}}}\frac{1}{i}(i+1)$

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

the simplest function $g(n)$ possible.

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

b$.{\displaystyle \underset{i=2}{\overset{n-1}{}}}lg{i}^2$

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

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

The sample variance of $n$ measurements $x_1,$dots,$x_n$ can be computed as either

$\frac{{\displaystyle \underset{i=1}{\overset{n}{}}}(x_i-(\stackrel{}{x}){)}^2}{n-1},$ where $\stackrel{}{x}=\frac{{\displaystyle \underset{i=1}{\overset{n}{}}}{x}_i}{n}$

or

$\frac{{\displaystyle \underset{i=1}{\overset{n}{}}}{x}_i^2-\frac{({\displaystyle \underset{i=1}{\overset{n}{}}}{x}_i{)}^2}{n}}{n-1}$

Find and compare the number of divisions, multiplications, and additions$/$

subtractions $($additions and subtractions are usually bunched together$)$ that

are required for computing the variance according to each of these formulas.

Consider the following algorithm.

ALGORITHM Mystery$(n)$

$//$Input: A nonnegative integer $n$

Slarr$0$

for ilarr$1tondo$

$,$SlarrS$+i*i$

return $S$

a$.$ What does this algorithm compute?

b$.$ What is its basic operation?

c$.$ How many times is the basic operation executed?

d$.$ What is the efficiency class of this algorithm?

e$.$ Suggest an improvement, or a better algorithm altogether, and indicate its

efficiency class. If you cannot do it$,$ try to prove that, in fact, it cannot be

done.