Reference no: EM131662026

Question: Occasionally, multiplying the sizes of nested loops can give an overestimate for the Big-Oh running time. This result happens when an innermost loop is infrequently executed. Repeat Exercise for the following program fragment:

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

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

          if( j % i == 0)

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

                   sum++;

Exercise: For each of the following program fragments, do the following:

a. Give a Big-Oh analysis of the running time.

b. Implement the code and run for several values of N.

c. Compare your analysis with the actual running times.