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

  • $\begingroup$ What are your thoughts? What have you tried? $\endgroup$ – D.W. Oct 6 '16 at 17:16
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.