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^{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) 50n^{3 }+ n^{2} + log n + n +10000
b) 2n^{5 }+100n^{2 }+1000log n
c) 200n + n^{2} log n
d) 10log n + n^{2} log n +10n4
5. Describe the information flow among DNAs, RNAs, and proteins