Method hasTwoTrueValues returns true if at least two values in an array of Boole
ID: 3622961 • Letter: M
Question
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 and give explanation.
1) public boolean hasTwoTrueValues( boolean [] arr)
{
int count = 0;
for( int i = o; i < arr.length; i++ )
if( arr[ i ] )
count++;
return count >=2;
}
2) public boolean hasTwoTrueValues( boolean [] arr )
{
for( int i = o; i < arr.length; i++ )
for( int j= i +1; j< arr.length; j++)
if( arr[ i ] && arr[ j ] )
return true;
return false;
}
3) public boolean hasTwoTrueValues( boolean [] arr)
{
for( int i = o; i < arr.length; i++ )
if( arr[ i ] )
for( int j= i +1; j< arr.length; j++)
if( arr[ j ] )
return true;
return false;
}
Explanation / Answer
1) public boolean hasTwoTrueValues( boolean [] arr)
{
int count = 0; O(1) = Constant Time.
for( int i = o; i < arr.length; i++ ) O(n) since the loop goes from 0 - n.
if( arr[ i ] ) O(1) = Constant Time.
count++; O(1) = Constant Time.
return count >=2; O(1) = Constant Time.
}
Therefore your Big-Oh is O(1) + O(n)(O(1)O(1))
= O(1) + O(n)
= O(n)
2) public boolean hasTwoTrueValues( boolean [] arr )
{
for( int i = o; i < arr.length; i++ ) O(n) since the loop goes from 0 - n.
for( int j= i +1; j< arr.length; j++) O(n) since the loop goes from 1 - n. O(n-1) = O(n)
if( arr[ i ] && arr[ j ] ) O(1) = Constant Time.
return true; O(1) = Constant Time.
return false; O(1) = Constant Time.
}
Therefore your Big-Oh is [O(n)] x (O(n) x (O(1)x(O(1)) ) )
= O(n) x O(n)
= O(n^2)
3) public boolean hasTwoTrueValues( boolean [] arr)
{
for( int i = o; i < arr.length; i++ ) O(n) since the loop goes from 0 - n.
if( arr[ i ] ) O(1) = Constant Time.
for( int j= i +1; j< arr.length; j++) O(n) since the loop goes from 1 - n.
if( arr[ j ] ) O(1) = Constant Time.
return true; O(1) = Constant Time.
return false;O(1) = Constant Time.
}
Therefore your Big-Oh is [O(n)] x ( O(1) x ( O(n) x ( O(1) x O(1) ) ) ) + O(1)
= O(n) x ( O(1) x O(n) ) + O(1)
= O(n^2) + O(1)
= O(n^2)