CSC 313 Data Structures Exam 3 Fall 2016 3 of 9 11· (3pts) T he complexity of Me

Question

CSC 313 Data Structures Exam 3 Fall 2016 3 of 9 11· (3pts) T he complexity of MergeSort satisfies the following recursive formula A. T(n) = 2T(n/2) + ?(n2) B. T(n) T(n/2) + e(n) C. T(n) 2T(n2)+e(n) 12. (3pts) Any algorithm that uses only element comparison to sort an input of n elements has lower bound complexity of A. (n2) B. 2(n2 log n) D. It depends on the algorithm 13. (3pts) Any algorithm that uses only comparison of adjacent elements to sort an input of n elements has lower bound complexity of B. (n2 log n) C. ?(n*) D. It depends on the algorithm

Explanation / Answer

Solution:

11)

D)

T(n)= 2T(n/2) + n

Explanation:

Since there are two recursive calls dividing an array of size n, so the recurrence will be as mentioned above.

12)

It depends on the algorithm

Explanation:

For example, insertion sort takes O(n) time if the number of inversions is required is less.

13)

A is correct.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---