JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (August/September - 2021 - R18)

Randomized Quick Sort is a variation of the standard Quick Sort algorithm where the pivot element is chosen randomly from the array instead of always picking the first or last element. This randomization ensures that the algorithm achieves an average-case time complexity of O(n log n) regardless of the input distribution, effectively preventing the worst-case O(n²) performance on already sorted or nearly sorted arrays.

The algorithm follows these steps:

• Select a random index between the current low and high bounds.
• Swap the element at the random index with the element at the high index to treat it as the pivot.
• Perform the standard partition procedure to place the pivot in its correct sorted position, such that all elements to the left are smaller and all elements to the right are larger.
• Recursively apply the same process to the left and right sub-arrays.

By picking a random pivot, the probability of consistently hitting the worst-case partition is extremely low, making the algorithm robust for practical applications.

Asymptotic notations are used to describe the growth rate of algorithms as the input size n approaches infinity.

Big-O Notation (O): Provides an asymptotic upper bound. A function f(n) is O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. It represents the worst-case complexity. Example: 3n + 2 is O(n).

Omega Notation (Ω): Provides an asymptotic lower bound. A function f(n) is Ω(g(n)) if there exist positive constants c and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀. It represents the best-case complexity. Example: 3n + 2 is Ω(n).

Theta Notation (θ): Provides an asymptotic tight bound. A function f(n) is θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. It occurs when the algorithm's upper and lower bounds are the same. Example: 3n + 2 is θ(n).