Consider the following method, whose implementation is shown: // Precondition: m
ID: 670902 • Letter: C
Question
Consider the following method, whose implementation is shown:
// Precondition: m represents matrix with N rows, N columns in each row,
//elements are increasing in each column, elements are increasing
// Postcondition: returns true if some element in m stores val;
//returns false otherwise
public static boolean contains( int [ ] [ ] m, int val ) {
int N = m.length;
for( int row = 0; row < N; row++ )
for( int col = 0; col < N; col++)
if( m[ row] [ col ] = = val )
return true;
return false;
}
An example of a matrix that satisfies the stated precondition is
int [ ] [ ] m1 = { { 4, 6, 8 },
{ 5, 9, 11, },
{ 7, 11, 14 } };
a. What is the running time of contains?
b.Suppose it takes 4 seconds to run contains on a 100-by-100 martix. Assuming that low-order terms are negligible, how long will it take to run contains on 400-by-400 matrix?
c. Suppose contains is rewritten so that the algorithm performs a binarysearch on each row (binary search takes O(logn) time to search for an element in a sorted array of n elements), returning true if any of the row-searches succeed, and false otherwise. What is the running time of this revised version of contains?
Explanation / Answer
1) public static boolean contains( int [ ] [ ] m, int val )
2) {
3) int N = m.length;
4) for( int row = 0; row < N; row++ )
5) for( int col = 0; col < N; col++)
6) if( m[ row] [ col ] = = val )
7) return true;
8) return false;
9) }
a) Consider the above given method, which takes a square matrix as input and searches a value in the matrix. For this, the method checks each element in the matrix with the given value. If the matrix contains the value, method returns true, false otherwise.
In the worst case(the element is the last element in the matrix or the given element is not in the given matrix), the method accesses and checks all N*N=N2elements in the matrix. The checking happens in the line 6, which enclosed by two for loops, each run N times. Thus, the line 6 is the dominant expression than any other expression in the method and runs O(N2) times in the worst case.
The lines 3, 7 and 8 executes in constant time. That is in O(1).
However, the worst case running time of the given method is O(N2).
b) It is given that, the matrix of size 100-by-100 can be accessed in 4 seconds.
The total elements in the matrix of 100-by-100 = 10,000
The total elements in the matrix of 400-by-400 = 16 X 10, 000. (Input size increases 16 times)
Thus, the method ‘contains’ takes time to access the matrix of 400 X 400 = 16X4=64 seconds.
c)
It is given that, the modified method ‘contains’ runs binary search on one row in O(log N) and there are N rows.
Thus, for running binary search on N rows= N X O (log N)= O(N log N)