New Enroll in RBI Grade B New Batch - Starts on May 21

    Question

    A software development team is implementing a sorting

    function for a large dataset in their project. They decide to use the quick sort algorithm to optimize performance. However, they observe that the function occasionally takes much longer to execute, especially when the dataset is sorted in ascending or descending order before being processed. Based on this scenario, what is the time complexity of the quick sort algorithm in its worst case? 
    A O(n) Correct Answer Incorrect Answer
    B O(n log n) Correct Answer Incorrect Answer
    C O(log n) Correct Answer Incorrect Answer
    D O(n²) Correct Answer Incorrect Answer
    E O(n³) Correct Answer Incorrect Answer

    Solution

    The quick sort algorithm, which follows a divide-and-conquer approach, usually achieves an average time complexity of O(n log n) by dividing an array into smaller subarrays, sorting each recursively. However, the algorithm’s performance heavily depends on how well it chooses the pivot element for each partition. When the pivot is consistently chosen poorly—such as always selecting the smallest or largest element in a sorted or nearly sorted array—the partitions become unbalanced, leading to a worst-case time complexity of O(n²). In this scenario, where the data is already ordered, the quick sort algorithm must process each element within increasingly unbalanced partitions, leading to nested recursive calls that significantly slow down execution. The other options are incorrect for the following reasons: • Option 1 (O(n)) is incorrect because quick sort does not exhibit linear performance, even in optimal conditions. Sorting generally requires more than O(n) operations. • Option 2 (O(n log n)) represents the best and average cases of quick sort when the partitions are balanced, which reduces the number of levels in the recursion tree. • Option 3 (O(log n)) is incorrect as it typically represents the time complexity of searching algorithms like binary search, not sorting algorithms. • Option 5 (O(n³)) is much higher than quick sort’s worst-case complexity and would imply an excessive number of operations that do not apply to the algorithm's nature.

    Practice Next

    Relevant for Exams: