Data Structures and Algorithms

1. For each of the following program fragments, give an analysis of the running time using Big-Oh notation. Do not give formulas, but analyze every line to calculate the running time, e.g. sum = 0 is equal to 1 unit time ...

b.

sum = 0;

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

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

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

sum++;

c.

sum = 0; for( i = 0; i < n²; i++) for( j = 0; j < i; j++) sum++;

d,

sum = 0;

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

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

sum++;