fg @® @ oonro7mini2 sec G)+ Which sorting algorithm has the worst-case time complexity of...
Fujitsu technical mcq question, verified with a worked answer. Free to practise - no sign-up.
fg @® @ oonro7mini2 sec G)+ Which sorting algorithm has the worst-case time complexity of O(nA2) but is often used for its simplicity with small datasets? - A) Quick Sort - B) Merge Sort - C) Bubble Sort - D) Radix Sort
Show answer & explanation
Answer: C. Bubble Sort
Bubble Sort is a simple comparison-based algorithm with a worst-case time complexity of O(n²), making it inefficient for large datasets but easy to implement for very small ones.
Step-by-step Derivation:
Step 1: Analyze the time complexities of the given options.
- Quick Sort: Average case O(n log n), Worst case O(n²). However, it is generally used for large datasets due to its efficiency, not primarily for 'simplicity with small datasets' in the context of O(n²) algorithms.
- Merge Sort: Worst case O(n log n). This does not match the O(n²) requirement.
- Bubble Sort: Worst case O(n²) and Average case O(n²). It is the quintessential 'simple' algorithm taught for small datasets.
- Radix Sort: Time complexity is O(nk), where k is the number of digits. This is linear relative to n and does not match O(n²).
Step 2: Compare the requirements. The question asks for an algorithm with O(n²) worst-case complexity and a reputation for simplicity with small datasets.
Step 3: Bubble Sort fits both criteria perfectly: it uses nested loops resulting in n * (n-1) / 2 comparisons, leading to O(n²) complexity, and is widely recognized as the simplest sorting algorithm to implement.