Sorting and Searching Algorithms Flashcards
1
Q
What is the time complexity of Merge Sort?
A
O(n log n) in all cases.
2
Q
What is the worst-case complexity of Quick Sort?
A
O(n²), but it has an average complexity of O(n log n).
3
Q
What is binary search, and what is its time complexity?
A
A divide-and-conquer search algorithm with O(log n) complexity.
4
Q
What is the best and worst-case time complexity of linear search?
A
Best: O(1) (first element is the target), Worst: O(n).
5
Q
What is the worst-case scenario for Quick Sort?
A
When the pivot is always the smallest or largest element → O(n²) complexity.
6
Q
What is the best sorting algorithm for nearly sorted data?
A
Insertion Sort (O(n)).
7
Q
What is the best-case complexity of Binary Search?
A
O(1) (if the middle element is the target).
