gotchaMinor
What is the difference between expected cost and average cost of an algorithm?
Viewed 0 times
thewhatexpectedaveragedifferencealgorithmbetweenandcost
Problem
While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost stands for.I think we take care of likelihood of an event while finding expected cost unlike average cost.
Solution
In short, the average is the expected value of the uniform distribution.
If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is
$\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$
given some random distribution for random variable $X$.
Average runtime is more specific and corresponds to
$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}_n|} \cdot \sum_{x\in\mathcal{X}_n} T(x)$
or, in other words, the expected runtime given a uniform distribution over inputs of the same size.
Since we usually use the uniform distribution the terms are often used interchangeably in algorithm analysis.
One famous exception is the analysis of binary search trees. As opposed to averaging height over all rooted binary trees, we calculate the expected height w.r.t. the uniform distribution of different insert sequences ("random permutation model"), which assigns some (shapes of) trees a higher probability than others. That is not a technical detail: the average height of rooted binary trees is in $\Theta(\sqrt{n})$ whereas the expected height of BSTs in the random permutation model is in $\Theta(\log n)$.
If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is
$\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$
given some random distribution for random variable $X$.
Average runtime is more specific and corresponds to
$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}_n|} \cdot \sum_{x\in\mathcal{X}_n} T(x)$
or, in other words, the expected runtime given a uniform distribution over inputs of the same size.
Since we usually use the uniform distribution the terms are often used interchangeably in algorithm analysis.
One famous exception is the analysis of binary search trees. As opposed to averaging height over all rooted binary trees, we calculate the expected height w.r.t. the uniform distribution of different insert sequences ("random permutation model"), which assigns some (shapes of) trees a higher probability than others. That is not a technical detail: the average height of rooted binary trees is in $\Theta(\sqrt{n})$ whereas the expected height of BSTs in the random permutation model is in $\Theta(\log n)$.
Context
StackExchange Computer Science Q#24220, answer score: 4
Revisions (0)
No revisions yet.