Description
1. Order the following functions by growth rate (5 points)
N
√𝑁
N
1.5
N
2
NlogN
NloglogN
Nlog2N
Nlog(N2
)
2/N
2
N
37
N
2
logN
N
3
Indicate which of the functions grow at the same rate.
2. For each of the following code fragments give running time analysis (Big Oh) (12 points)
a. sum =0;
for ( i=0; i < n ; i++)
sum++;
b. sum =0;
for( i = 0; i < n; i++)
for(j = 0; j < i ; j++)
sum++;
c. sum =0;
for( i = 0; i < n; i++)
for( j = 0; j < i *i ; j++)
for( k = 0; k