Difference between revisions of "TADM2E 2.45"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
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>.  
+
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 &lt;math&gt;n&lt;/math&gt;:
+
To compute expected value we sum this quantity for <math>n</math>:
  
&lt;math&gt;\sum_{i=1}^{n} \frac{1}{i}&lt;/math&gt;
+
<math>\sum_{i=1}^{n} \frac{1}{i}</math>
  
and recognize this as the definition of the &lt;math&gt;n^{th}&lt;/math&gt; &lt;i&gt;Harmonic number&lt;/i&gt;
+
and recognize this as the definition of the <math>n^{th}</math> <i>Harmonic number</i>
  
&lt;math&gt;H(n) = \sum_{i=1}^{n} \frac{1}{i} \sim \ln n&lt;/math&gt;
+
<math>H(n) = \sum_{i=1}^{n} \frac{1}{i} \sim \ln n</math>
  
so our expected value approaches &lt;math&gt;\ln n&lt;/math&gt; as &lt;math&gt;n&lt;/math&gt; grows large.
+
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]]''

Revision as of 18:23, 11 September 2014

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