JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (September - 2021 - R16)

Quick Sort is a divide and conquer algorithm that picks an element as a pivot and partitions the array around the chosen pivot. The process involves three steps: Divide by choosing a pivot and partitioning the array into two sub-arrays such that elements in the left sub-array are less than or equal to the pivot and elements in the right are greater; Conquer by recursively applying the algorithm to the sub-arrays; and Combine, which is trivial as the sub-arrays are sorted in place.

Algorithm:

1. Choose an element as pivot (e.g., the last element).
2. Partition the array: maintain an index i, iterate through the array, and swap elements smaller than the pivot to the front.
3. Place the pivot in its correct sorted position.
4. Recursively sort the left and right partitions.

Sorting the list [4, 2, 0, 8, 7, 1, 3, 6]:

1. Initial: [4, 2, 0, 8, 7, 1, 3, 6], Pivot = 6. Partitioning results in [4, 2, 0, 1, 3] | 6 | [8, 7].
2. Left partition [4, 2, 0, 1, 3], Pivot = 3. Partitioning results in [2, 0, 1] | 3 | [4].
3. Left partition [2, 0, 1], Pivot = 1. Partitioning results in [0] | 1 | [2].
4. Right partition [8, 7], Pivot = 7. Partitioning results in [7] | 8.
5. Final sorted list: [0, 1, 2, 3, 4, 6, 7, 8].

Best Case Time Efficiency:

The best case occurs when the pivot consistently divides the array into two nearly equal halves. The recurrence relation is:

Using the Master Theorem, where a=2, b=2, and f(n)=n, we have n^log_b(a) = n^1. Since f(n) = Θ(n^log_b(a)), the best-case time complexity is O(n log n).

To solve the recurrence T(n) = 3T(n/3) + n using the substitution method, we first guess the asymptotic bound. Based on the Master Theorem structure, we hypothesize that T(n) = O(n log n).

We must prove that T(n) ≤ c n log n for some constant c > 0. We assume the inductive hypothesis holds for smaller values, specifically T(n/3) ≤ c(n/3) log(n/3).

Substituting this into the recurrence:

Simplifying the expression:

For the inequality T(n) ≤ cn log n to hold, we require:

This holds true when 1 - c log 3 ≤ 0, which implies c ≥ 1/log 3. By choosing a constant c that satisfies this condition and selecting an appropriate base case, we confirm that T(n) = O(n log n).