Sorting, Searching & Big-O Flashcards

Radix Sort processes digits from least significant to most significant. This variant is called:

Answer: LSD Radix Sort

LSD (Least Significant Digit) Radix Sort processes from the rightmost digit first and is stable, producing correct results after all passes.

Which of the following is NOT a characteristic of Bucket Sort?

Answer: It is a comparison-based sort

Bucket Sort is a non-comparison-based sort that distributes elements into buckets and sorts each bucket individually.

The recurrence T(n) = 2T(n/2) + O(n) describes which algorithm's complexity?

Answer: Merge Sort

Merge Sort splits the array into two halves (2T(n/2)) and merges in O(n) time, giving T(n) = 2T(n/2) + O(n), which resolves to O(n log n).

What is the best-case time complexity of Bubble Sort when an early-exit optimization is used?

Answer: O(n)

With an early-exit flag, Bubble Sort detects a fully sorted array in one pass and terminates, achieving O(n) best-case.

Which of the following describes the key property used by Ternary Search?

Answer: It divides the search space into three equal parts

Ternary Search divides the search space into three parts using two midpoints, eliminating one-third of candidates per iteration for O(log₃ n) complexity.

When Quick Sort always picks the smallest or largest element as the pivot, its time complexity degrades to:

Answer: O(n²)

Consistently bad pivot selection causes maximally unbalanced partitions, creating n recursive calls each processing n elements for O(n²) total.

Which of the following sort algorithms is adaptive, meaning it performs fewer operations when the input is partially sorted?

Answer: Timsort

Timsort (used in Python and Java) detects existing runs in the input and merges them, performing O(n) on already-sorted data.