Give an analysis of the running time for each of the following programs:

1. sum = 0;

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

sum++;

2. sum = 0;

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

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

3. sum = 0;

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

{

}