Algorithm Design Manual Problem 1–1

A lighter problem from the Algorithm Design Manual (second edition).

Problem

Show that a + b can be less than min(a, b).

Thoughts

  • a + b < min(a, b)
  • If a < b : a + b < a
  • If b < a : a + b < b

Cases

  1. a < b
    1. a + b < a
    2. b < a — a
    3. b < 0
  2. b < a 1. a + b < b 2. a < b — b 3. a < 0

Solution

If `a` and `b` are less than `0` then the addition of both is less than the minimum of the pair.

Example

a <- (-2)
b <- (-3)
minimum <- min(a, b) // (-3)
sum <- (-2) + (-3) // (-5)
sum < minimum // Matches condition for completion