Monday, May 9, 2011

0/1 matrix

Given a 0/1 matrix A of size n x n, find the row with the maximum number of 0s

3 comments:

  1. How are we measuring the quality of a solution? If it's the usual worst-case asymptotic time complexity, then you can't go below O(n^2).

    ReplyDelete
  2. We can sort it, but this doesn't change the argument that any algorithm will have to read all the matrix elements.

    Or are you saying that it's somehow sorted initially?

    ReplyDelete