(a) Give an analysis of the running time of the following program fragment and obtain the running time (Big-Oh), i.e. if the order of complexity is O(f(n)), then f(n)=?.

sum = 0;

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

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

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

++sum;

(b) An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following (assume low-order terms are negligible)?

a. linear , b. O(N logN), c. quadratic , d. cubic