1. Order the following functions by growth rate
N
√𝑁
N1.5
N2
NlogN
NloglogN
Nlog2N
Nlog(N2)
2/N
2N
37 N2logN
N3
Indicate which of the functions grow at the same rate.
2. For each of the following code fragments give running time analysis (Big Oh)
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<j; k++) sum++;
3. What is the time complexity of the below function?
void fun(int n, int arr[])
{
int i = 0, j = 0; for(; i < n; ++i)
while(j < n && arr[i] < arr[j]) j++;
}
4. An algorithm takes o.5 ms for input size 100. How long will it take for input size 500 if the running time is the following (assume lower order terms are negligible) a. linear
b. O(N log N)
c. quadratic
d. cubic
5. Show that 𝑋62 can be computed with only eight multiplications
6. Give an efficient algorithm to determine if there exists an integer i such that 𝐴𝑖 = 𝑖 in an array of N distinct integers, sorted in ascending order. What is the running time of given algorithm?
7. Give an efficient algorithm along with running time analysis to find the minimum subsequence sum (Assume the minimum sum is either 0 or a negative value)
