|
|
| Line 1: |
Line 1: |
| − | The expected number of times the assignment to <i>tmp</i> is made is the sum of the probabilities that the <math>n^{th}</math> element is the <i>minimum</i>. If we assume the minimum is distributed uniformly in our sequence then the probability any given element is the minimum is <math>1/n</math>.
| |
| | | | |
| − | Expected time is E(n) = E(n-1) + 1/n, E[1] = 0
| |
| − |
| |
| − | To compute expected value we sum this quantity for <math>n</math>:
| |
| − |
| |
| − | <math>\sum_{i=1}^{n} \frac{1}{i}</math>
| |
| − |
| |
| − | and recognize this as the definition of the <math>n^{th}</math> <i>Harmonic number</i>
| |
| − |
| |
| − | <math>H(n) = \sum_{i=1}^{n} \frac{1}{i} \sim \ln n</math>
| |
| − |
| |
| − | so our expected value approaches <math>\ln n</math> as <math>n</math> grows large.
| |
| − |
| |
| − | ''Return to [[Algo-analysis-TADM2E]]''
| |
