Which sorting algorithm has best-case time complexity of O(n) when input is already sorted?
- Quick Sort
- Merge Sort
- Bubble Sort
- Heap Sort
Answer: Bubble Sort
Bubble Sort with optimization (stop if no swaps in a pass) achieves O(n) best-case for already sorted input. However, average/worst-case remains O(n²). For exams: know trade-offs - Bubble (simple, inefficient), Quick (fast average, worst O(n²)), Merge (stable, O(n log n) always), Heap (in-place, O(n log n)).