# TADM2E 2.45

From Algorithm Wiki

Revision as of 18:23, 11 September 2014 by Algowikiadmin (Talk | contribs)

The expected number of times the assignment to *tmp* is made is the sum of the probabilities that the $ n^{th} $ element is the *minimum*. If we assume the minimum is distributed uniformly in our sequence then the probability any given element is the minimum is $ 1/n $.

Expected time is E(n) = E(n-1) + 1/n, E[1] = 0

To compute expected value we sum this quantity for $ n $:

$ \sum_{i=1}^{n} \frac{1}{i} $

and recognize this as the definition of the $ n^{th} $ *Harmonic number*

$ H(n) = \sum_{i=1}^{n} \frac{1}{i} \sim \ln n $

so our expected value approaches $ \ln n $ as $ n $ grows large.

*Return to Algo-analysis-TADM2E*