# Envyless location using divide and conquer

We have a cake of length $$n$$ and we have two arrays $$A$$ and $$B$$ of size $$n$$. The two arrays have order like below. $$A[0], $$B[0]>B[1]>\dots >B[n]$$. We define a envyless location as a cut in the cake where it satisfies $$A[i]=B[i]$$. For example, $$A=[1,2,3,4,5,6,7]$$ and $$B=[7,6,5,4,3,2,1]$$, $$A[3]=B[3]=4$$, therefore, cutting the cake at length 4 makes the cut envyless. If the algorithm finds an envyless location it returns it's location, and if the envyless location does not exist, it returns null. I am trying to use divide and conquer to solve this problem with worst-case runtime of $$O(\log n)$$.

I have tried the following procedure and failed. First, divide the cake in half. Find the mid point of the splitted cake and compare $$A[mid]$$ and $$B[mid]$$. If found, terminate and return the location. If not found, keep on dividing and comparing.
I expected this to run on $$O(\log n)$$ time but it cannot because for example, if $$A=[1,2,3,4,5,6]$$ and $$B=[20,11,9,8,7,6]$$, the envyless location is at location 6, and the algorithm needs to do $$n$$ comparison, making the algorithm to run at $$O(n\log n)$$.

Any help will be very helpful.

If $$A[\text{mid}] < B[\text{mid}]$$ then you can recurse on $$A[\text{mid}+1, \dots, n]$$ and $$B[\text{mid}+1, \dots,n]$$ since, if an envyless cut exists, it must be after location $$mid$$.
The situation $$A[\text{mid}] > B[\text{mid}]$$ is symmetric and you can recurse on $$A[0, \dots, \text{mid}-1]$$ and $$B[0, \dots, \text{mid}-1]$$.
The resulting algorithm takes time $$T(n) \le T(\lfloor n/2 \rfloor) + O(1)$$, which has solution $$T(n) = O(\log n)$$.
• Shouldn't the algorithm recurse on $A[0,…,mid−1]$ and $B[0,…,mid−1]$ when $A[mid] > B[mid]$? For example, when $A=[98,99,100,101,102]$ and $B=[98,4,3,2,1]$, $A[mid] > B[mid]$ and the envyless point can exist only on before mid. May 22 at 3:02