Difference between revisions of "TADM2E 2.45"
From Algorithm Wiki
(Recovering wiki) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
| − | The expected number of times the assignment to | + | 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 | Expected time is E(n) = E(n-1) + 1/n, E[1] = 0 | ||
| − | To compute expected value we sum this quantity for | + | 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 | + | 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 | + | so our expected value approaches <math>\ln n</math> as <math>n</math> grows large. |
''Return to [[Algo-analysis-TADM2E]]'' | ''Return to [[Algo-analysis-TADM2E]]'' | ||
Latest revision as of 13:11, 24 July 2020
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
