Sorting, Searching & Big-O Flashcards

What is the lower bound for comparison-based sorting algorithms?

Answer: O(n log n)

Any comparison-based sort must make at least Ω(n log n) comparisons in the worst case, proven via decision tree argument.

Which searching algorithm works by jumping ahead by a fixed step and then performing linear search in the block?

Answer: Jump Search

Jump Search divides a sorted array into blocks of size √n, jumps to find the right block, then searches linearly within it for O(√n) complexity.

What does amortized analysis describe?

Answer: The average cost per operation over a sequence of operations

Amortized analysis averages the cost of operations over a sequence, smoothing out occasional expensive operations like dynamic array resizing.

Shell Sort improves upon Insertion Sort by:

Answer: Sorting distant elements first using a gap sequence

Shell Sort uses a decreasing gap sequence to compare and swap elements far apart, reducing the total number of shifts needed.

What is the time complexity of interpolation search in the best case on uniformly distributed data?

Answer: O(log log n)

Interpolation Search achieves O(log log n) on uniformly distributed sorted data by estimating the probe position proportionally.

Which sorting algorithm is typically used for sorting linked lists efficiently?

Answer: Merge Sort

Merge Sort works well on linked lists because merging two sorted lists is O(n) without random access, unlike Quick Sort which needs efficient pivot access.

What is the space complexity of Merge Sort?

Answer: O(n)

Merge Sort requires O(n) auxiliary space to hold the two halves being merged at each level of recursion.