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.
