Give the Big-Oh for the running time of each code fragment. a. double power( dou

ID: 3590851 • Letter: G

Question

Give the Big-Oh for the running time of each code fragment.

a.
double power( double x, int n ) {
double result = 1.0;
for( int i = 0; i < n; i++ )
result *= x;
return result;
}

b.
bool hasTwoTrueValues( bool array [], int n ) {
for( int i = 0; i < n; i++ )
for( int j = i + 1; j < n; j++ )
if( array[ i ] && array[ j ] )
return true;
return false;
}

c.
bool hasTwoTrueValues( bool array [], int n ) {
int count = 0;
for( int i = 0; i < n; i++ )
if( array[ i ] )
count++;
return count >= 2;
}

d.
bool hasTwoTrueValues( bool array [], int n ) {
for( int i = 0; i < n; i++ )
if( array[ i ] )
for( int j = i + 1; j < n; j++ )
if( array[ j ] )
return true;
return false;
}

Explanation / Answer

The for loop n times.

Hence, Time Complexity = O(n)

When ,

i = 0 , inner for loop runs n - 1 times

i = 1 , inner for loop runs n - 2 times

i = n - 1 , inner for loop runs 0 times

Hence, number of times both loops run = 0 + 1 + 2 + ... + (n-1) = 1 + 2 + ... + (n-1)

= ( n - 1 ) ( n - 1 + 1 ) ( 2 * ( n - 1 ) + 1 ) / 6

( using sum of squares of n natural numbers = n (n + 1)(2n + 1) / 6 )

Hence, time complexity = O(n ^ 2)