TADM2E 2.45 - Revision history

Matt: Undo revision 958 by Erecua (talk)

2020-07-24T13:11:23Z

Undo revision 958 by Erecua (talk)

Matt: Undo revision 959 by Erecua (talk)

2020-07-24T13:11:03Z

Undo revision 959 by Erecua (talk)

Erecua at 12:10, 24 July 2020

2020-07-24T12:10:34Z

Erecua at 12:10, 24 July 2020

2020-07-24T12:10:20Z

Matt: Undo revision 806 by Hdyldhdlgzos (talk)

2020-07-23T15:57:01Z

Undo revision 806 by Hdyldhdlgzos (talk)

Hdyldhdlgzos: Blanked the page

2020-07-16T06:27:30Z

Blanked the page

Algowikiadmin: Recovering wiki

2014-09-11T18:23:09Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:40Z

Recovering wiki

New page

The expected number of times the assignment to tmp is made is the sum of the probabilities that the <math>n^{th}</math> 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 <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> Harmonic number

<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]]''

@@ 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-4) + 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 <math>n</math>:

@@ Line 5: / Line 5: @@
 To compute expected value we sum this quantity for <math>n</math>:
-<math>\sum_{i=4}^{n} \frac{1}{i}</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>

@@ Line 5: / Line 5: @@
 To compute expected value we sum this quantity for <math>n</math>:
-<math>\sum_{i=1}^{n} \frac{1}{i}</math>
+<math>\sum_{i=4}^{n} \frac{1}{i}</math>
 and recognize this as the definition of the <math>n^{th}</math> <i>Harmonic number</i>

@@ 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
+Expected time is E(n) = E(n-4) + 1/n, E[1] = 0
 To compute expected value we sum this quantity for <math>n</math>:

← Older revision		Revision as of 06:27, 16 July 2020
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]]''~~

← Older revision	Revision as of 15:57, 23 July 2020
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]]''

@@ Line 1: / Line 1: @@
-The expected number of times the assignment to &lt;i&gt;tmp&lt;/i&gt; is made is the sum of the probabilities that the &lt;math&gt;n^{th}&lt;/math&gt; element is the &lt;i&gt;minimum&lt;/i&gt;. If we assume the minimum is distributed uniformly in our sequence then the probability any given element is the minimum is &lt;math&gt;1/n&lt;/math&gt;.
+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 &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]]''