Selection: minimum and maximum, second largest, k-th smallest

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Counting sort time? from Lesson 3.3.2
• Expected comparisons of quicksort? from Lesson 3.2.2
• Recursion tree for T(n/5) + T(7n/10) + n? from Lesson 1.2.4

1 · The Hook

🎣

To find the median salary, you don't need to sort all salaries. To find the best and worst scores, you need fewer comparisons than finding them separately. Selection problems have exact optimal comparison counts, and GATE asks for them: 3n/2 − 2 for min and max, n + ⌈log n⌉ − 2 for the second largest.

2 · Predict First

🤔

Finding the maximum of n numbers takes n − 1 comparisons, and the minimum another n − 1. Can you find both with fewer than 2n − 2 comparisons?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Yes: compare the elements in pairs first. The larger of each pair competes for the maximum, the smaller for the minimum. That is 3 comparisons per 2 elements: about 3n/2.

Minimum (or maximum)

Exactly n − 1 comparisons; this is optimal (every non-minimum must lose at least once).

Minimum and maximum together

Pair up the elements: 1 comparison inside each pair, then the larger against the current max and the smaller against the current min.

• n even: 3n/2 − 2 comparisons.
• n odd: 3⌊n/2⌋ comparisons. (In general 3⌈n/2⌉ − 2.)

Second largest

Run a tournament (knockout): n − 1 comparisons find the largest. The second largest must have lost directly to the largest, and the largest played ⌈log n⌉ matches. A second knockout among those takes ⌈log n⌉ − 1 comparisons. Total: n + ⌈log n⌉ − 2 (optimal). n = 16: 18; n = 100: 105.

k-th smallest (selection)

• Sort, then index: Θ(n log n).
• Quickselect: partition like quicksort, recurse into one side only. Average Θ(n) (T(n) = T(n/2) + n on average); worst Θ(n²).
• Median of medians: groups of 5, recursive median of the group medians as pivot. Guarantees ≥ 3n/10 elements on each side: T(n) ≤ T(n/5) + T(7n/10) + Θ(n) → Θ(n) worst case.
• k smallest elements with a heap: build a min-heap Θ(n), extract k times: Θ(n + k log n).

4 · Visual

Tournament for the maximum of 8 (7 comparisons)

 a  b   c  d   e  f   g  h
  \/     \/     \/     \/
  ab     cd     ef     gh
    \   /         \   /
    abcd           efgh
          \      /
           winner           the winner played log 8 = 3 matches;
                            2nd largest is among those 3 losers: 2 more comparisons
                            total 7 + 2 = 9 = 8 + 3 - 2

5 · Worked Examples

Example 1 Easy

Comparisons to find both the minimum and maximum of 100 numbers (pairing method)?

Solution

3 × 100/2 − 2 = 148.

Example 2 Medium

Comparisons to find the largest and second-largest of 16 numbers (optimal)?

Solution

16 + 4 − 2 = 18.

Example 3 GATE

The median of n elements can be found in worst-case time:

Solution

Θ(n) (median of medians); quickselect is Θ(n) only on average.

6 · GATE Traps

⚠️

• Min + max: 3n/2 − 2 for even n, 3⌊n/2⌋ for odd n.
• Second largest: n + ⌈log n⌉ − 2, not 2n − 3.
• Quickselect's worst case is Θ(n²); only median of medians is worst-case linear.
• k smallest via heap: Θ(n + k log n), sorted output included.

7 · Memory Hook

🧠

"Pairs for min and max (3 per 2), tournament for second (n + log n − 2)."

8 · Connect the Dots

Phase 3 is complete: every sort, its counts and limits, and selection. Phase 4 generalises two ideas you have already used: splitting into subproblems (divide and conquer) and making the locally best choice (greedy).

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markMin and max (even)

Comparisons to find both the minimum and maximum of 50 elements by pairing?

Numerical answer: ________

Q2NAT1 markMin and max (odd)

Comparisons to find both the minimum and maximum of 7 elements by pairing?

Numerical answer: ________

Q3NAT2 marksSecond largest

Minimum comparisons to find the second largest of 1,000 elements?

Numerical answer: ________

Q4MCQ1 markSelection worst case

Which finds the k-th smallest of n elements in Θ(n) worst-case time?

• (A) Median of medians
• (B) Heapsort then index
• (C) Insertion sort then index
• (D) Quickselect with first-element pivot

Q5NAT1 markMinimum

Comparisons needed to find the minimum of 64 elements?

Numerical answer: ________

10 · Rule Card

• Min (or max): n − 1. Min and max: 3n/2 − 2 (n even), 3⌊n/2⌋ (n odd).
• Second largest: n + ⌈log n⌉ − 2 (tournament).
• Quickselect: average Θ(n), worst Θ(n²). Median of medians: worst Θ(n).
• k smallest with a heap: Θ(n + k log n).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

minimum with n − 1 comparisonssimultaneous min and maxtournament methodsecond largest n + ⌈log n⌉ − 2selection problemquickselectmedian of mediansk smallest via heap

12 · Answer Vault