New Click here to Enroll for SIDBI MSME Expert Class by ex-GM, SBI on Nov 24

    Register

    Question

    Which all statements are correct about Sorting

    A Bubble sort has O(n^2) as best case time complexity Correct Answer Incorrect Answer
    B selection sort has O(n^2) as best case time complexity Correct Answer Incorrect Answer
    C Insertion sort has O(n^2) as best case time complexity Correct Answer Incorrect Answer
    D Radix sort has O(n+K) as best case time complexity Correct Answer Incorrect Answer
    E Only b and d are correct Correct Answer Incorrect Answer

    Solution

    Option 5: only b and d Explanation

    1. Bubble sort has O(n^2) as best case time complexity
      • This statement is incorrect . The best case time complexity for Bubble Sort is O(n) , which occurs when the array is already sorted. In such cases, Bubble Sort can detect the sorted array early and terminate.
    2. Selection sort has O(n^2) as best case time complexity
      • This statement is correct . Selection Sort always has a time complexity of O(n^2) , regardless of the initial ordering of the elements. This is because it always goes through the entire list to find the minimum element for each position.
    3. Insertion sort has O(n^2) as best case time complexity
      • This statement is incorrect . The best case time complexity for Insertion Sort is O(n) , which occurs when the array is already sorted. In such cases, each insertion requires only one comparison.
    4. Radix sort has O(n+K) as best case time complexity
      • This statement is correct . Radix Sort has a time complexity of *O(d(n + k))**, where d is the number of digits in the largest number and k is the range of the digit (base of the number system). In many cases, it is simplified to O(n + k) if the number of digits d is considered a constant.
    Correct Option Option 5: only b and d is correct because:
    • Selection Sort has O(n^2) as its best case time complexity.
    • Radix Sort has O(n + k) as its best case time complexity

    Practice Next