Selection Problem - Matrix

Let A be a real valued matrix of order n*n already stored in memory. Its (i, j)-th element is denoted by a[i, j]. The elements of the matrix A satisfy the following property:

Let the largest element in row i occur in column Li. Now, for any two rows i1, i2, if i1<i2, then Li1<=Li2.

(a)

2 6 4 5 3

5 3 7 2 4

4 2 10 7 8

6 4 5 9 7

3 7 6 8 12

(b)

Row I l(i)

1 2

2 3

3 3

4 4

5 5

Figure shows an example of (a) matrix A, and (b) the corresponding values of l_i for each row i.

Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.