Quick Sort Experiment

1. What is the best-case time complexity of Quick Sort when each partition divides the array into two approximately equal parts?

O(n \log n)

Explanation

O(n^2)

Explanation

O(n)

Explanation

O(\log n)

Explanation

2. What is the average-case time complexity of Quick Sort when the pivot selection usually produces reasonably balanced partitions?

O(n^2)

Explanation

O(n \log n)

Explanation

O(n)

Explanation

O(\log n)

Explanation

3. Which situation produces the worst-case time complexity of Quick Sort?

a: The pivot repeatedly divides the array into nearly equal parts. Explanation

Explanation

b: The pivot is selected randomly and produces balanced partitions most of the time. Explanation

Explanation

c: The pivot repeatedly produces one very small partition and one partition containing almost all remaining elements. Explanation

Explanation

d: The array contains elements that are all distinct. Explanation

Explanation

4. Consider the recurrence

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

for Quick Sort. What time complexity does this recurrence represent?

O(n)

Explanation

O(n^2)

Explanation

O(\log n)

Explanation

O(n \log n)

Explanation

5. In the worst case, Quick Sort can be represented by the recurrence

T(n) = T(n - 1) + O(n)

. What is the resulting time complexity?

O(n^2)

Explanation

O(n \log n)

Explanation

O(n)

Explanation

O(\log n)

Explanation

6. What is the typical auxiliary space complexity of recursive Quick Sort when the partitions are reasonably balanced?

O(n^2)

Explanation

O(n)

Explanation

O(\log n)

Explanation

O(1)

in every recursive implementation Explanation

Explanation

7. In the worst case, what can happen to the auxiliary space used by recursive Quick Sort?

a: It becomes

O(\log n)

regardless of the pivot selection. Explanation

Explanation

b: It can become

O(n)

because the recursion depth can become linear. Explanation

Explanation

c: It becomes

O(n^2)

because every comparison creates a stack frame. Explanation

Explanation

d: It becomes

O(1)

because Quick Sort is always in-place. Explanation

Explanation

8. Which statement correctly compares Quick Sort with Merge Sort and Heap Sort in terms of standard time complexity?

a: Quick Sort has

O(n \log n)

worst-case time, while Merge Sort has

O(n^2)

worst-case time. Explanation

Explanation

b: Quick Sort has

O(n)

average-case time, while Heap Sort has

O(\log n)

worst-case time. Explanation

Explanation

c: Quick Sort has

O(n \log n)

average-case time but

O(n^2)

worst-case time, while Merge Sort and Heap Sort have

O(n \log n)

worst-case time. Explanation

Explanation

d: All three algorithms have

O(n)

worst-case time. Explanation

Explanation

9. Why does Quick Sort have

O(n \log n)

time when its partitions are balanced?

a: There are approximately

\log_2(n)

partitioning levels, and the total partitioning work across each level is

O(n)

. Explanation

Explanation

b: There are

n

partitioning levels, and each level performs constant work. Explanation

Explanation

c: The algorithm performs only

\log_2(n)

comparisons in total. Explanation

Explanation

d: The algorithm does not need to process every element during partitioning. Explanation

Explanation