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 n³ = O(n²) ?

Is n³ = W(n²)?

Arrange the following expressions by growth rate from slowest to fastest.

4n²

n!

log₃n

3ⁿ

20n

2

log₂n