Lower Bound for Time Complexity of Pairing Problem

Question

Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, the second smallest in X matched with second smallest in Y and so on. i.e the algorithm will yield the pairs: $(x_{1},y_{1}),...,(x_{i},y_{i}),...,(x_{n},y_{n})$, $x_{i}$ being the i'th smallest element in X.
I need to find the lower bound for the time complexity of the problem.

I think the lower bound is O(n) because when the two arrays are sorted we only need to match the elements with the same index in each array - so we'll need to go over n indices = O(n). But this just proves the existence of the possible time complexity of O(n) and doesn't prove it's the minimum.

Is O(n) the lower bound? And if so what is the proof?

Answer 1

This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your convention.

---

The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)$.

For the upper bound, we can solve the problem by sorting both lists.

For the lower bound, if we fix the second array to be $y_i = i$, then we are essentially sorting the first array $X$. Stated differently, there is a reduction from sorting to this problem, with the same value of $n$ and no extra comparisons. Since sorting takes $\Omega(n\log n)$ comparisons in the worst case, this problem also requires $\Omega(n\log n)$ comparisons.

---

So far we have only discussed worst-case complexity, and the same argument also works for average-case complexity. The best-case complexity is $\Theta(n)$. This means that we can find a correct algorithm that runs in time $O(n)$ on some input; and every correct algorithm requires $\Omega(n)$ comparisons on every input.

For the upper bound, consider the algorithm that first checks whether both $X$ and $Y$ are increasing ($2(n-1)$ comparisons). If so, it returns the mapping $(x_i,y_i)$. Otherwise, it transfers control to an arbitrary correct algorithm.

The lower bound follows from the same reduction from sorting, since sorting is known to require at least $n-1$ comparisons on any input. Indeed, the same argument used to prove this shows that any algorithm for the pairing problem requires $2(n-1)$ comparisons on any input.