Algorithm analysis - Data Structures and Problem Solving Using Java - page 222

Consider the following method, whose implementation is shown:

5.28

// 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 r = 0; r < N; r++ )
for( int c = 0; c < N; c++ )
if( m[ r ][ c ] == 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

matrix. Assuming that low-order terms are negligible, how long
will it take to run contains on a 400-by-400 matrix?

c. Suppose contains is rewritten so that the algorithm performs a

binary search on each row, returning true if any of the row-
searches succeed, and false otherwise. What is the running time
of this revised version of contains ?

Method hasTwoTrueValues returns true if at least two values in an array
of Booleans are true. Provide the Big-Oh running time for all three
implementations proposed.

5.29

// Version 1
public boolean hasTwoTrueValues( boolean [ ] arr )
{

int count = 0;

for( int i = 0; i < arr.length; i++ )
if( arr[ i ] )
count++;

return count >= 2;

}