Question: Suppose we have an array $A$ of size $n$ all with distinct values. We define a pair $(a,b)$ with $a < b$ if for each $a < i < b$ we have that $A[i] < \min{\{A[a], A[b]\}}$. That is, all the values corresponding to the indices between $(a,b)$ in the array are strictly less than the value corresponding to both the value at index $a$, and the value at index $b$. So, if $A = [7,3,9,4]$ then one such pair is $(1,3)$ since $A[2] = 3 < \min\{A[1], A[3]\} = 7$.
I wish to design an $O(n\log n)$ time algorithm which calculates the total number of pairs in any such array.
My attempt: My inkling is that this can be solved using divide and conquer. If $T(n)$ is our recursive function which finds the total number of pairs based on an array of length $n$. We note that $T(2) = 1$ and so it is a safe assumption to believe that our recursive algorithm will satisfy the following recursion relation: $$ T(n) = \begin{cases} \Theta(1) &\text{if } n = 2, \\ 2T(n/2) + f(n) &\text{if }n>2. \end{cases} $$ This recursion basically states that we divide our array into two sub-arrays (one containing everything before and including the mid-point, and another containing everything after) and recurse on each (the $2T(n/2)$ term) so we find all pairs which reside entirely within the left sub-array, and pairs which reside entirely within the right sub-array. Additionaly, we have an extra function $f(n)$ which calculates the number of pairs which pass the midpoint.
For me to prove that this recursive divide and conquer is indeed $O(n\log n)$ I need to prove that $f(n) = \Theta(n)$ so I can invoke the Master Theorem. However, this has proved to be extremely difficult and I'm unsure how I can figure out a method which takes exactly $n$ steps which ensures I find all pairs which cross the mid-point of the array. Absolutely any help, suggestions or hints would much appreciated. Thank you!
Suppose your array is this: 7, 4, 1, 2 / 6, 5, 8, 3, 9
and the slash is where you've split it in two.
Go through the left block from right to left, to pick out the increasing sequence. In this case you get 2, 4, 7.
Do the same for the right block but from left to right, which gives 6, 8, 9 in this case.
Any pair that crosses the boundary must consist of one number from each list. Constructing these lists takes linear time.
The lowest number of these two lists is the 2 on the left. This number can only make a pair with the lowest number on the other list. So add 1 to the count of the total number of pairs, and remove the 2, so you are left with lists 4, 7 and 6, 8, 9.
Then repeat this procedure till the end.
So the whole sequence of steps looks like this:
(2), 4, 7 ; 6, 8, 9: Add 1 to the total
(4), 7 ; 6, 8, 9: Add 1 to the total
7 ; (6), 8, 9: Add 1 to the total
(7) ; 8, 9: Add 1 to the total
; 8, 9: End
Clearly you must stop as soon as one of the lists becomes empty.
Again this is at most linear time complexity, since the number of steps is no more than the total length of the lists.
You could save some time by working out how many numbers remain in the non-empty list at the end of the procedure (e.g. using binary search to find where the highest number on one list fits into the other list) and thereby find the number of pairs directly, but since making the lists is linear in the first place there is little point.