Geek asks and answers

How can I find the lower bound for sorting matrices?

Consider the problem of sorting the matrix n x n(i.e., rows and columns are in ascending order). I want to find the lower and upper bounds of this problem.

I found this to O(n^2 log n)be by simply sorting the elements and then outputting the first elements nas the first row, the next elements nas the second row, etc. however, I want to prove that as well Omega(n^2 log n).

Having tried smaller examples, I think I must prove that if I can solve this problem using less comparisons n^2 log(n/e), this will violate the lower bound log(m!)for comparisons needed to sort the elements m.

Any ideas on how to prove this?

+5
source share
1 answer

Take a look at http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms .

Your problem sounds like you are just sorting n² elements instead of n, so “O (n² log n²)” might be valid for mergesort, for example.

If the first n elements in the first row do not need to be sorted by yourself, it can be faster, but not necessary, it depends on the algorithm.

And last but not least, the attempt of some examples does not prove something, especially the small ones, where the statistics do not take effect (they do not even indicate something)

0
source

More articles:


All Articles