For each of the following six program fragments: a. Give an analysis of the runn

Question

For each of the following six program fragments:

a. Give an analysis of the running time (Big-Oh will do).

.

.

(1)

sum = 0;

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

. ++sum;

.

(2)

sum = 0;

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

. for( j = 0; j < n; ++j )

. ++sum;

.

(3)

sum = 0;

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

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

. ++sum;

(4)

sum = 0;

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

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

. ++sum;

(5)

sum = 0;

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

. for( j = 0; j < i * i; ++j )

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

. ++sum;

(6)

sum = 0;

for( i = 1; i < n; ++i )

. for( j = 1; j < i * i; ++j )

. if( j % i == 0 )

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

. ++sum;

Explanation / Answer

(1)

sum = 0;

for( i = 0; i < n; ++i ) ========> Loop runs for n time overall

. ++sum;========> it runs for n time because of for loop

=> Overall time complexity is O(n)

(2)

sum = 0;

for( i = 0; i < n; ++i )========> Loop runs for n time overall

for( j = 0; j < n; ++j )========> Loop runs for n time itself and n time because of above loop so n2 overall

++sum;========> runs for n2 time because of for loop

=> Overall time complexity is O(n2)

(3)

sum = 0;

for( i = 0; i < n; ++i )========> Loop runs for n time overall

for( j = 0; j < n * n; ++j )========> Loop runs for n2 time itself and n time because of above loop so n3 overall

++sum;

=> Overall time complexity is O(n3)

(4)

sum = 0;

for( i = 0; i < n; ++i )=======> Loop runs for n time overall

for( j = 0; j < i; ++j )=======> Loop runs for 1 + 2 + 3 + 4 ......n => n(n+1)/2

++sum;

=> Overall time complexity is O(n2)

(5)

sum = 0;

for( i = 0; i < n; ++i )=======> Loop runs for n time overall

for( j = 0; j < i * i; ++j )=======> Loop runs for 12 + 22 + 33 + 42 ......n2 => n(n+1)(2n+1)/6

for( k = 0; k < j; ++k )=======> Loop runs for 12  + 22 + 33 + 42 ......n2 => n(n+1)(2n+1)/6 and n time because of outer loop so its n4 times

++sum;

=> Overall time complexity is O(n4)

(6)

sum = 0;

for( i = 1; i < n; ++i )======> Loop runs for n time overall

for( j = 1; j < i * i; ++j )=======> Loop runs for 12  + 22 + 33 + 42 ......n2 => n(n+1)(2n+1)/6

if( j % i == 0 )

for( k = 0; k < j; ++k )=======> Loop runs for 12  + 22 + 33 + 42 ......n2 => n(n+1)(2n+1)/6 and n time because of outer loop so its n4 times

++sum;

=> Overall time complexity is O(n4)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.