JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (August - 2022 - R16)

Randomized algorithms utilize a source of random bits to guide their execution, ensuring that the algorithm's behavior depends on both the input and the random choices made. They are primarily classified into two types:

1. Las Vegas Algorithms: These algorithms always produce the correct result or inform the user about a failure. The randomness affects only the running time, not the correctness of the output. An example is Randomized QuickSort, where the choice of the pivot is random, but the sorted output is always correct.
2. Monte Carlo Algorithms: These algorithms have a deterministic running time but a probability of producing an incorrect answer. The error probability can be reduced by running the algorithm multiple times or increasing the computational effort. An example is the Miller-Rabin primality test, which determines if a number is prime with a certain probability of error.

The QuickSort algorithm follows a divide-and-conquer strategy by selecting a pivot element and partitioning the array such that elements smaller than the pivot are on the left and larger are on the right.

Algorithm:

QuickSort(A, low, high) {
  if (low < high) {
    p = Partition(A, low, high)
    QuickSort(A, low, p - 1)
    QuickSort(A, p + 1, high)
  }
}

In the worst-case scenario, the partition process consistently results in highly unbalanced splits, such as when the pivot is always the smallest or largest element in the array (e.g., sorting an already sorted array with the first or last element as the pivot). This leads to a recursion tree of depth n, where n is the number of elements.

The recurrence relation for the worst case is:

This simplifies to:

Summing this series results in T(n) = Θ(n²). Thus, the worst-case time complexity of QuickSort is quadratic.