Develop and analyze an iterative version of Sequential Search (Search(A, k, p, r) that returns the position of k in the sorted integer array A[p ... r]. If k is not found, the algorithm returns -1. For your algorithm perform the following specific tasks: Give pseudocode for your iterative Search(A, k, p, r) algorithm. NOTE: You may not use global variables in your algorithm. Perform a line-by-line analysis of your algorithm and derive a precise expression T(n) for the running time, where n is the length of the array. You may assume that each line of pseudocode takes unit time. Describe the situation resulting in the best-case running time of your algorithm and derive an expression for T(n) in this case. Also, give an asymptotic expression for T(n). Describe the situation resulting in the worst-case running time of your algorithm and derive an expression for T(n) in this case. Also, give an asymptotic expression for T(n). Develop and analyze a recursive version of Binary Search (BSearch(A, k, p, r)) algorithm that uses a divide-and-conquer approach to perform a search for k (returns the position of k in the array or return -1 if k is not found) in which the algorithm divides the sorted array in half and calls itself recursively on each half. For your algorithm perform the following specific tasks: Give pseudocode for your recursive BSearch(A, k, p, r) algorithm. NOTE: You may not use global variables in your algorithm. Perform a line-by-line analysis of your algorithm. Describe the situations resulting in the best-case and worst-case performances of your algorithm. Derive a precise recurrence for T(n) in the worst case, and solve the recurrence. The following chart shows the run time of algorithms that use f(n) operations to run on a computer where each operation takes one second to execute. Fill in the blanks in the chart. n f(n)=log2n f(n)=n f(n)=n log2n f(n)=n2 f(n)=2n 10 3.3s 10s 33.0s 100s 1024s 20 50 100 1000 10000 For each of the following, answer "yes", "no", or "cannot tell". Explain your reasoning. Is n3 = O(n2) ? Is n3 = W(n2)? Arrange the following expressions by growth rate from slowest to fastest. 4n2 n! log3n 3n 20n 2 log2n