Solution for NPTEL, Introduction to Algorithm and Analysis Week 1 MCQs

1. Algorithm A, B have running time 7n²+4n+5 and 3n² respectively. Then in big theta approximation

A. Both have same complexity

B. A asymptotically beats B

C. B asymptotically beats A

D. None

 

A. Both have same complexity

2. Two main measure of efficiency of an algorithm

A. processor and memory

B. time and space

C. date and space

D. date and capacity

Answer :B. time and space

3. If p(x)=a₁x+…+a_mx^m (x>1) then p(x)=

A. O(x^m)

B. O(mx)

C. Both

D. None

Answer :A. O(xm)

4. If t₁(n) = O(f(n)), t₂(n)= O(g(n)). Then t₁(n).t₂(n)=_____

A. O(f(n)

B. O(g(n))

C. O(f(n)g(n))

D. None of the above

Answer :C. O(f(n)g(n))

5. In worse case analysis which one is true?

A. Insertion sort is better than merge sort

B. Merge sort and Insertion sort have same running time complexity

C. Merge sort is better than insertion sort

D. None of these

Answer :C. Merge sort is better than insertion sort

6. Insertion sort has

A. Worse case running time Θ(n²) ,average case running time Θ(n²).

B. Worse case running time Θ(n), average case running time Θ(n).

C. Worse case running time Θ(n2), average case running time Θ(n)

D. Worse case running time Q(n), average case running time Q(n²).

Answer : A. Worse case running time Θ(n2),averagecase running time Θ(n2).

7. Consider an array of elements A[5]= {5,4,3,2,1} , what are the steps of insertion sort

A. 4 5 3 2 1, 3 4 5 2 1, 2 3 4 5 1, 1 2 3 4 5

B. 5 4 3 1 2, 5 4 1 2 3, 5 1 2 3 4, 1 2 3 4 5

C. 4 3 2 1 5, 3 2 1 5 4, 2 1 5 4 3, 1 5 4 3 2

D. 4 5 3 2 1, 2 3 4 5 1, 3 4 5 2 1, 1 2 3 4 5

 

Answer :A. 4 5 3 2 1,3 4 5 2 1,2 3 4 5 1,1 2 3 4 5

 

8. Merge sort has worse case running time

A. Θ(nlogn)

B. Θ(n)

C. Θ(1)

D. None

Answer :A. Θ(nlogn)

9. Big Theta gives

A. Lower Bound

B. Upper Bound

C. Both Lower and Upper Bounds

D. None of the above

Answer :C. Both Lower and Upper Bounds

10. When the array is already sorted in ascending order then running time using insertion sort is

A. Θ(n)

B. Θ(1)

C. Θ(n³).

D. None

Answer :A. Θ(n)