Problem One (8 points) In your textbook, the binary search is presented in iteration format. Please rewrite the binary algorithm in recursive format. You should write the algorithm in the follow format. The italic parts are the parts you need to modify.

Input: Describe what is the input of the algorithm,

Output: Describe what is the output of the algorithm.

Procedure BinarySearchRecursive(argument list)

Algorithm details

End Procedure

Note: You are not required to write code. In fact, you should not write code here. You should just write the algorithm. Also, you may need another algorithm so called the driver for BinarySearchDriver which simply call BinarySearchRecursive appropriately to search the given array for given key.

Problem Two (8 points, 4 points each) Consider the following array:

12, 13, 15, 15, 16, 16, 19, 23, 25, 26, 30, 31 ,32

1. If use linear search algorithm from your textbook with search key 16, what is the return value?
2. If use binary search algorithm from your textbook with search key 16, what is the return value?

Problem Three (8 points, 4 points each)

1. Order the following big O notation, from the fastest running time to slowest running time.

1000, 2n, nlnn, 2n2, n,

2. Determine big O notation for function fn=1000n+0.1n2+nlnx