) For each of the following loop program fragments, give a Bio-oh

analysis of the running time (make your bound as tight as possible).

i) for( int i = 0; i < n; i++)

for( int j = 0; j < n * n; j++)

sum++;

ii) for( int i = 0; i < n; i++)

for( int j = 0; j < i; j++)

sum++;

iii) for ( int i = 0; i < n/2; i++)

for( int j =0; j < n * n; j++)

for( int k = 0; k < j; k++)

sum++;

iv) for ( int i = 1; i < n; i = i * 2 )

sum++;