Sorting and Searching Algorithms Flashcards
(12 cards)
What is the time complexity of Merge Sort?
O(n log n) in all cases.
What is the worst-case complexity of Quick Sort?
O(n²), but it has an average complexity of O(n log n).
What is binary search, and what is its time complexity?
A divide-and-conquer search algorithm with O(log n) complexity.
What is the best and worst-case time complexity of linear search?
Best: O(1) (first element is the target), Worst: O(n).
pivot
What is the worst-case scenario for Quick Sort?
When the pivot is always the smallest or largest element → O(n²) complexity.
What is the best sorting algorithm for nearly sorted data?
Insertion Sort (O(n)).
What is the best-case complexity of Binary Search?
O(1) (if the middle element is the target).
What is a brute-force sorting algorithm?
A naive method that checks all possible orderings of elements to find the sorted one—inefficient (O(n!)) and rarely used in practice.
How does Selection Sort work?
Repeatedly selects the minimum element and moves it to the front.
Time complexity: O(n²), in-place, not stable.
How does Insertion Sort work?
Builds a sorted list one item at a time by inserting each element into its correct position.
Time complexity: Best case O(n), worst case O(n²), in-place, stable.
How does Bubble Sort work?
Repeatedly swaps adjacent elements if they are in the wrong order.
Time complexity: O(n²), in-place, stable.
Which simple sorting algorithm is best for nearly sorted input?
Insertion Sort, as its best case is O(n).
