Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.

I found that it is $O(n^2logn)$ by just sorting the elements and then outputting the first $n$ elements as the first row, the next $n$ elements as the second row, and so on. However, I want to prove that it is also $\Omega(n^2logn)$.

After trying smaller examples, I think I should prove that if I can solve this problem using less than $n^2log(\frac{n}{e})$ comparisons, it would violates the $log(m!)$ lower bound for comparisons needed to sort $m$ elements. Any ideas on how to prove that?


Here is the argument I alluded to in my earliest comment. I claim that a sorted $n\times n$ matrix $A$ can be linearly sorted in $n^2 \log_2 n + O(n^2)$ comparisons. To do this, we maintain a vector $v$ which records up to $n$ values of $A$ in increasing order (and their corresponding locations $i,j$). Initially, take $v$ to be the first row of $A$.

We then iterate the following procedure $n^2$ times: output the least value of $v$, delete it from $v$, and insert into $v$ the entry directly underneath it in $A$ (if there is one). Since $v$ is sorted, finding the lowest value takes $0$ comparisons, but insertion of the new value requires a binary search on $v$, which is $\lceil \log_2 m \rceil \le \log_2 m + 1$ comparisons, where $m \le n$ is the length of $v$.

It should be clear that we never insert any value into $v$ before exhausting all smaller values, so if we iterate $n^2$ times this gives a linearly sorted list. The number of comparisons is at most $n^2 (\log_2 n + 1) = n^2 \log_2 n + O(n^2)$, proving the claim.

However, to sort an arbitrary matrix of $n^2$ elements requires at least $\log_2(n^2!)$ comparisons in the worst case, and this is equal to $n^2 \log_2 n^2 - O(n^2) = 2n^2 \log_2 n - O(n^2)$ . Therefore, getting from an arbitrary matrix to a sorted matrix must consume at least the difference of these two amounts of comparisons in the worst case, namely $n^2 \log_2 n - O(n^2)$.

  • $\begingroup$ I don't understand your conclusion (Therfore, ... ). How do you go from the problem of sorting the elements of a sorted matrix to the problem of sorting the matrix itself. Please, can you explain it to me? $\endgroup$ – Jiyda Moussa Feb 9 '13 at 9:41
  • $\begingroup$ @jiji777 Do you understand what the lower bound for sorting means? There is no comparison-based way to sort $n^2$ numbers without spending about $2n^2 \log n$ comparisons. Yet if we could matrix-sort cheaply it would only cost about half that many. $\endgroup$ – Erick Wong Feb 9 '13 at 15:00
  • $\begingroup$ No, I understand that. But if T(n) is the time spent to get from an arbitrary matrix to a sorted matrix and S(n) is the time spent to get from a sorted matrix to a sorted array. Shouldn't you prove that $S(n)$ cannot be done in less than $n^2logn$ to prove that $T(n) \geq n^2logn+log(n^2!)$. Is giving one algorithm that runs in $n^2logn$ sufficient or do we have to prove it for all algorithms? $\endgroup$ – Jiyda Moussa Feb 9 '13 at 20:21
  • $\begingroup$ @jiji777 You have it backwards. We know that $T(n) + S(n) \ge 2n^2 \log n$, because the RHS is how long it takes to go from arbitrary matrix to sorted list, and the LHS is one possible way of doing so. A lower bound for $S(n)$ wouldn't help at all to control $T(n)$. $\endgroup$ – Erick Wong Feb 9 '13 at 20:23
  • $\begingroup$ right. Ok, thanks. $\endgroup$ – Jiyda Moussa Feb 9 '13 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.