Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$. I proceed by assuming that it can be done faster than $n^2\log n$ and try to violate the $\log(m!)$ lower bound for comparisons needed to sort m elements. I have two conflicting answers:

  1. we can get a sorted list of the $n^2$ elements from the sorted matrix in $O(n^2)$ http://math.stackexchange.com/questions/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
  2. you can't get a sorted list from the matrix faster than $Ω(n^2\log(n))$ http://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-matrix-which-has-all-its-m-rows-sorted-and-n-columns-sorted

Which one is right?

share|improve this question
5  
As an aside, it irritates me when we see claims that "sorting is $\Omega(n\log n)$" but that do not specify the input model and the model of computation. Comparison sorting is $\Omega(n\log n)$. Sorting, in general, may be faster than that, for instance for strings (if $n$ is the total input length) or integers (in certain models of computation that allow constant time integer arithmetic operations). –  David Eppstein Feb 9 '13 at 21:03
2  
To be even more pedantic: Comparison sorting is not $\Omega(n\log n)$, because comparison sorting isn't a function from $\mathbb{R}$ to $\mathbb{R}$. Sorting requires $\Omega(n\log n)$ time in any binary decision tree model (not just comparisons). –  JɛffE Feb 9 '13 at 22:43
add comment

1 Answer 1

up vote 14 down vote accepted

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order.

It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you just need to make them sufficiently large. In particular, sorting the matrix implies sorting each one of these diagonals. The $i$th diagonal has $i$ entries, and as such $i!$ possible ordering. As such, a sorted matrix could define at least $X = \prod_{i=1}^n i!$ different orderings. It is now easy to verify that $\log_2 X = \Omega(n^2 \log n)$, implying that in the comparison model (and as Jeff points out below, in any binary decision tree model) at least this is a lower bound on the sorting time.

share|improve this answer
2  
Again, in any binary decision tree model, not just comparisons. –  JɛffE Feb 9 '13 at 22:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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