Data Structures & Algorithms Hashing & Sorting Flashcards

24 sample cards from the Hashing & Sorting deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. Give the recurrence relation for Merge Sort and its solution.

   $T(n) = 2T\!\left(\frac{n}{2}\right) + O(n)$, which by the Master Theorem solves to $T(n) = O(n \log n)$.

2. Describe the Quick Sort algorithm.

   Divide-and-conquer: choose a pivot, partition the array so smaller elements go left and larger go right of the pivot, then recursively sort the two partitions. The pivot ends in its final position.

3. State the best, average, and worst-case time complexity of Quick Sort.

   Best and average $O(n \log n)$; worst $O(n^{2})$ (e.g. already-sorted input with a poor pivot). Average space $O(\log n)$ for recursion; in-place, generally unstable.

4. How can Quick Sort's worst case be avoided?

   Use randomized pivot selection or the median-of-three rule, making the $O(n^{2})$ case extremely unlikely and giving expected $O(n \log n)$ performance.

5. Give the worst-case recurrence for Quick Sort with a maximally unbalanced pivot.

   $T(n) = T(n-1) + O(n)$, which solves to $T(n) = O(n^{2})$.

6. Describe the Heap Sort algorithm.

   Build a max-heap from the array, then repeatedly swap the root (maximum) with the last element, shrink the heap, and sift the new root down. This extracts elements in sorted order.

7. State the time and space complexity of Heap Sort.

   $O(n \log n)$ in best, average, and worst cases. In-place with $O(1)$ auxiliary space, but not stable.

8. What is the time complexity of building a heap from an unsorted array?

   $O(n)$ using the bottom-up heapify (sift-down) construction — tighter than the naive $O(n \log n)$ of repeated insertions.

9. For a 0-indexed binary heap array, give the index formulas for a node at index $i$.

   Left child $2i+1$, right child $2i+2$, parent $\left\lfloor \frac{i-1}{2} \right\rfloor$.

10. State the lower bound for comparison-based sorting and its justification.

    Any comparison sort requires $\Omega(n \log n)$ comparisons in the worst case. A decision tree with $n!$ leaves has height $\geq \log_2(n!) = \Theta(n \log n)$ by Stirling's approximation.

11. Why can Counting, Radix, and Bucket sorts beat the $\Omega(n \log n)$ bound?

    They are not comparison-based; they use the values themselves (as indices/digits/ranges) rather than pairwise comparisons, so the decision-tree lower bound does not apply.

12. Describe the Counting Sort algorithm.

    Count the occurrences of each key value in a range $[0,k]$, compute prefix sums to find output positions, then place each element into its sorted position using the counts.

13. State the time and space complexity of Counting Sort.

    Time $O(n + k)$ and space $O(n + k)$, where $k$ is the range of key values. It is stable and efficient only when $k = O(n)$.

14. Describe the Radix Sort algorithm (LSD variant).

    Sort the numbers digit by digit from least significant to most significant, using a stable sort (typically counting sort) on each digit. After processing all digits the array is fully sorted.

15. State the time complexity of Radix Sort.

    $O(d\,(n + b))$, where $d$ is the number of digits and $b$ is the base/radix. For fixed-width integers this is effectively $O(n)$.

16. Why must the per-digit sort used inside Radix Sort be stable?

    Stability preserves the ordering established by less significant digits when sorting on more significant digits; without it, LSD radix sort produces incorrect results.

17. Describe the Bucket Sort algorithm.

    Distribute the $n$ elements into $k$ buckets by value range, sort each bucket individually (often with insertion sort), then concatenate the buckets in order.

18. State the average and worst-case complexity of Bucket Sort.

    Average $O(n + k)$ when inputs are uniformly distributed across buckets; worst case $O(n^{2})$ when all elements fall into one bucket. Space $O(n + k)$.

19. Describe Linear Search and its complexity.

    Scan elements sequentially from start until the target is found or the list ends. Time $O(n)$ worst/average, $O(1)$ best; space $O(1)$. Works on unsorted data.

20. Describe the Binary Search algorithm and its precondition.

    On a sorted array, repeatedly compare the target to the middle element and discard the half that cannot contain it, halving the search space each step. Precondition: the array must be sorted.

21. State the time complexity of Binary Search and its recurrence.

    $O(\log n)$ time. Recurrence $T(n) = T\!\left(\frac{n}{2}\right) + O(1)$, solving to $T(n) = O(\log n)$. Space $O(1)$ iterative, $O(\log n)$ recursive.

22. Give a numerically safe formula for the midpoint in Binary Search and explain why.

    $\text{mid} = \text{low} + \frac{\text{high} - \text{low}}{2}$. This avoids the integer overflow that $\frac{\text{low}+\text{high}}{2}$ can cause for large indices.

23. Describe Ternary Search and its complexity.

    Split the range into three parts using two midpoints $m_1, m_2$ and discard two-thirds each step (on a sorted array, or to find the extremum of a unimodal function). Time $O(\log_3 n) = O(\log n)$.

24. Why is Binary Search generally preferred over Ternary Search despite both being $O(\log n)$?

    Ternary search does more comparisons per level ($\log_3 n$ levels but up to $2$ comparisons each, $\approx 2\log_3 n \approx 1.26\log_2 n$), so binary search performs fewer total comparisons.

What this deck covers

Hashing & Sorting flashcards FAQ