# TADM2E 2.45

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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