# 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?

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)$?

• What are your thoughts? What have you tried? – D.W. Oct 6 '16 at 17:16
• I understand now in general it's not true that $\langle f(g) \rangle \neq f(\langle g \rangle)$. I guess that fact that $f$ here is an algorithm's runtime led me to confuse expectation w/ the mode - $T(n)_{mode} = T(n_{mode})$? But I do understand why $\langle f(g) \rangle \neq f(\langle g \rangle)$. I feel dumb. – Tushar Rakheja Oct 6 '16 at 21:36

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$.