1. What is the best running time of any sorting algorithm if comparison is used?

a. O(log n)b. O(n)c. O(n log n)d. O(n²)e. O(n²logn)

2. Which of the following represents the recurrence relation of a quicksort with sorted inputs in increasing order when the last element is a pivot?

a. T(n) = T(n/2) + O(1) b. T(n) = T(n/2) + O(n) c. T(n) = 2* T(n/2) + O(n) d. T(n) = T(0) + T(n-1) + O(n) e. T(n) = T(n-1) + T(n-2) + O(1)

3. What is the worst-case depth of recursion tree for merge sort?

O(n) O(log n) O(nlog n) O(n2) O(n-1)

4. Which of the following can achieve a linear time for time complexity?

a. Mergesort b. Quicksort c. AVL sort d. Counting sort e. Bubble sort

5. Write a recurrence relation for the Merge sort and solve the running time.