From probability theory we know that the expected number of coin tosses required in order to get k heads is 2·k

• For a recursive call at depth d we expect
  • d/2 ancestors are good calls
    ⇒ size of input sequence for current call is  ≤ (¾)^d/2 · n
• Therefore,
  • the input of a recursive call at depth 2·log_4/3n has expected size 1
    ⇒ the expected recursion depth thus is O(log n)
• The total amount of work done at all the nodes of the same depth is O(n)