1. Order the following functions by growth rate: N, N, N1.5, N2, NlogN, N log log N, N log2 N, N log(N2), 2/N, 2N, 2N/2, 37, N2 log N, N3. Indicate which functions grow at the same rate.

2. For each of the following six program fragments, give an analysis of the running time (Big-Oh will do).

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

 ++sum; (2) sum = 0; 

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

 ++sum; (3) sum = 0; 

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

 ++sum; (4) sum = 0; 

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

 ++sum; (5) sum = 0; 

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

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

 (6) sum = 0; for( i = 1; i < n; ++i ) 

 for( j = 1; j < i * i; ++j ) if( j % i == 0 ) 

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