Alice and Bob want to split a log cake between the two of them. The log cake is n centimeters long and they want to make one slice with the left part going to Alice and the right part going to Bob. Both Alice and Bob have different values for different parts of the cake. In particular, if the slice is made at the i-th centimeter of the cake, Alice receives a value A[i] for the first i centimeters of the cake and Bob receives a value B[i] for the remaining n i centimeters of the cake. Alice and Bob receives strictly higher values for larger cuts of the cake: A[0] < A[1] < . . . < A[n] and B[0] > B[1] . . . > B[n]. Ideally, they would like to cut the cake fairly, at a location i such that A[i] = B[i], if it exists. Such a location is said to be envy-free. Example:

When A = [1, 4, 6, 10] and B = [20, 10, 6, 4] then 2 is the envy-free location, since A[2] = B[2] = 6. Your task is to design a divide and conquer algorithm that returns an envy-free location if it exists and otherwise, to report that no such location exists. For full marks, your algorithm should run in O(log n) time. Remember to:

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.