[SOLVED] CE3345 Assignment 2

1. Order the following functions by growth rate (5 points)

N

√𝑁

N1.5

N2

NlogN

NloglogN

Nlog²N

Nlog(N²)

2/N

2^N

37 N²logN

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) (12 points)

1. 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?                                (5 points)

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) (8 Points) linear
   1. O(N log N)
   2. quadratic
   3. cubic

5. Show that 𝑋⁶² can be computed with only eight multiplications (4 Points)

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? (8 Points)

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) (8 points)