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.
