1. Prove using induction: 1 + 3 + 5 +···+ (2n − 1) = n^2
2. Give a big-O estimate for the number of operations (where an operation is an addition or multiplication) used in this segment of an algorithm:
for i:=1 to 3
for j:=1 to 4
Explain your answer.
3. Suppose that there are n = 2^k teams in an elimination
tournament, where there are n/2 games in the first round,
with the n/2 = 2^k−1 winners playing in the second round,
and so on. Develop a recurrence relation for the number
of rounds in the tournament.
4. Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.
5. a) Let f(n) and g(n) be functions from the set of positive integers to the set of real numbers. State the definition of the fact that f(n) is O(g(n)).
b) Use your definition from (a) to prove that 1^2 + 2^2 + ……. + n^2 is O(n^3).