1. The following is a recursive algorithm to calculate the *k*-th power of 2.

Input k a natural number

Output kth power of 2

Algorithem:

If k =0then return 1

Else return 2* power _of_2(k-1)

Please review the decomposition of a recursive algorithm described in slide #17 (week 1, 3-Recursion-IterativeAlgorithms.pdf). Please show the decomposition whne k = 5.

2. Please write an iterative algorithm to calculate the *k*-th power of 2. This iterative algorithm should be equivalent to the recursive algorithm in question 1.

3. Reorder the following time efficiencies from largest to smallest:

a) *n*log *n*

b) 52

c) *n *+ *n*^{2 }+ *n*^{3} + *n*^{4}

d) *n*^{3}

e) *n*^{5} log *n*

4. Determine the big-O notations for the following time efficiencies and reorder them from largest to smallest:

a) 50*n*^{3 }+ *n*^{2} + log *n *+ *n *+10000

b) 2*n*^{5 }+100*n*^{2 }+1000log *n*

c) 200*n *+ *n*^{2} log *n*

d) 10log *n *+ *n*^{2} log *n *+10*n*4

5. Describe the information flow among DNAs, RNAs, and proteins