3. Big-Oh Induction (4 points) Use strong induction to prove that T(n) T(n) T(n/2) +10 (for n 2 2) O(log n) where T(1) 90 and 4. Recursive Algorithm and Analysis (6 points) Suppose company X has hired you as a software engineer. Company X is desperate to improve the run time of their software. Rather than allow you to usc the standard binary scarch algorithm, company X demands you create a new version. Since recursively dividing the array into two parts is so cfficient for scarching, the bigwigs at company X conclude dividing the array into three parts will be even more efficient. This new "3-ary" search divides the given sorted array into 3 equal sized sorted subarrays. It finds which subarray will contain the given value and then recursively searches that subarray. If the given value is in the array you should return true. Otherwise you should return false (1) (2 points) Write up this new recursive algorithm using pscudocode (IIint: For simplicity you can assume the number of elements in the given sorted array, n, is a power of 3) (2) (1 point) Create a recurrence to represent the worst case run time of our new "3-ary" scarch from the pseudocode (IIint: The worst case run time occurs when the given value is not in the array (3) (2 points) Use master theorem to solve your above recurrence relation (1) (1 point) Compare this asymptotic run time to that of binary scarch Does our new algorithm perform significantly better than binary search? (5) (0 points - Just for fun) Try comparing the constants of binary scarch and "3-ary" search. You can use the change of base formula for log to convert both to log,n