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) nlog n

b) 52

c) n + n² + n³ + n⁴

d) n³

e) n⁵ log n

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

a) 50n³ + n² + log n + n +10000

b) 2n⁵ +100n² +1000log n

c) 200n + n² log n

d) 10log n + n² log n +10n4

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