Chapter 5.1

Total order is a binary relation on some set X, which is antisymmetric, transitive, and a connex relation.

A binary relation R is a total order on set X if the following statements hold for all a, b and c in X:

• Antisymmetry: If \(aRb\) and \(bRa\), then \(a = b\).
• Transitivity: If \(aRb\) and \(bRc\), then \(aRc\).
• Connexity: Either or both of \(aRb\) or \(bRa\) hold(s).

We could simply obtain the three statements from the assumption that we are always able to determine which candidate is best, hence we know a total order on the ranks of the candidates.

• \(T(a, b) = \Theta(b - a)\) running time

  RANDOM-INT(a, b)
      for i = a to b
          a = a + RANDOM(0, 1)
      return a
  

• \(T(a, b) = \Theta(\lg (b - a))\) running time

  RANDOM-INT(a, b)
      while a < b
          mid = (a + b) // 2
          if RANDOM(0, 1) == 0
              b = mid
          else a = mid + 1
      return a
  

UNBIASED-RANDOM()
    while True:
        x = BIASED-RANDOM()
        y = BIASED-RANDOM()
        if x > y
            return 1
        if x < y
            return 0

The expected running time is \(T(n) = \Theta(\frac{1}{2p(1-p)})\).