Week 5: String Algorithms, Approximation, Randomisation, Ethics (129)

n … size of array

For a recursive call at depth d we expect
- d/2 ancestors are good calls since each is good with probabilty 0.5
  ⇒ expected 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)

Hence the expected runtime is O(n·log n)