World's most popular travel blog for travel bloggers.

Is it or is it not correct to say that the expected runtime of an algorithm is its runtime on the expected problem size? Why?

, , No Comments
Problem Detail: 

Say we have an algorithm that takes time $T$ to process a problem of size $n$.

Is $\langle T(n)\rangle $ = $T(\langle n\rangle)$?

Asked By : Tushar Rakheja
Answered By : Yuval Filmus

In general, it does not hold that $\DeclareMathOperator{\EE}{\mathbb{E}}\EE[f(X)] = f(\EE[X])$. For example, suppose that $X=0$ with probability $1/2$ and $X=1$ with probability $1/2$, and that $f(x) = x^2$. Then $\EE[f(X)] = 1/2$ whereas $f(\EE[X]) = 1/4$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback