As we have studied in the class, in Binary Search Problem $($BSP$),$ input array A is divided into two

subproblem at each iteration. Here is the illustration of input length in recursive calls:

$n$

$\frac{n}{2}$

We know that the complexity of BSP is $O(logn).$ What happens if we divide the problem into $3,4,$ or

$5$ subproblems at each iteration? Assume that we divide the given problem into $3$ subproblems. Then

the above image will be like as follows:

n

$\frac{n}{3}$

If the problem is divided into $4$ or $5,$ or more subproblems, we will have much smaller sub problems

in each iteration. Is this going to improve the complexity of search? That is$,$ can we find the key

element that we are looking in the given array in a smaller number of comparisons? You will

implement BSP where the given array is divided into $3$ sub problems instead of $2.$

$(40$ pts$)$ Implement BSP where the given input is divided into $3$ subproblems in each iteration.

$(20$ pts$)$ Place appropriate counter, say c$,$ to determine number of lines your algorithm is

executing. Tabulate input size n and counters for both BSP algorithms for $n=10,100,1000,$

$10000,1000000.$ Note that BSP with two subproblems already exists on the blackboard. So$,$

you can download and run both algorithms on the same sorted array and determine their

number of lines executed.

$(20$ pts$)$ Give a complete complexity analysis of your algorithm.

$(20$ pts$)$ Is this new algorithm better than $($more efficient than$)$ the original? Why?