A. Find a theta notation for the best-case time required by the following algorithm:

is_key(s, n, key) {

for i = 1 to n - 1

for j = i + 1 to n

if (si + sj ==key)

return 1

else

return 0

}

B. Trace the algorithm of the Insertion Sort for the input

40 18 134 60

Algorithm: the insertion sort

Input: s, n

Output: s (sorted)

insertion_sort(s, n) {

for i = 2 to n {

val = si // save si so it can be inserted into the correct place

j = i - 1

// if val < sj, move sj right to make room for si

while (j 1 val < sj) {

sj+1 = sj

j = j 1

}

sj+1 = val // insert val

}

}

D. Let consider that

1 + 2 + + n = Wn² + Xn + Y

For all n, and for some constant W, X and Y.

1. Assuming that this is true, plug in n = 1, 2, 3 to obtain three equations in the three unknowns W, X and Y.

2. Solve for W, X and Y with the three equations obtained in the previous question.

3. Prove using the mathematical induction that the statement is true.

E. Use the mathematical induction to show that (T_n is a Fibonacci Sequence):

Tn2 = Tn-1 Tn+1 + (-1)n+1 for all n 2