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


  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).

  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?