Qn 1 Arrange the following functions in ascending order of growth. This means, if function g(n) immediately follows f(n) in your list, then it should be the case that f(n) 2 O(g(n)). You should give a proof of f(n) 2 O(g(n)) for every consecutive pair of functions in your ordered list.

Qn 2 Prove by induction on n that the following expression is true:

Qn 3 Consider the following iterative algorithm

a) What does this algorithm compute?

b) What is its basic operation?

c) How many times is the basic operation executed? (You must formally justify this answer using the mathematical analysis discussed in class.)

d) What is the efficiency class of this algorithm?

e) Suggest an improvement or a better algorithm altogether and indicate its efficiency class.

Qn 5 Solve the following recurrence relations (show your work):

a) x(n) = 4x(n 1) for n > 1 where x(1) = 3.

b) x(n) = x(n 1) + 5 for n > 1 where x(1) = 2.

c) x(n) = x(n 1) + n for n > 1 where x(1) = 1.

d) x(n) = 3x(n=2) + n for n > 1 where x(1) = 0:5 (solve for n = 2k).

e) x(n) = nx(n 1) for n > 0 where x(0) = 1.