Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for sums such that evaluating $f(x)$ is easy and fast, but evaluating


is slow and hard.

To be more scientific, evaluating $f(x)$ takes time $O(n)$, but evaluating the definite sum of $f(x)$ takes time $\Omega(m) >> O(n)$.


I'd prefer functions $f(x)$ that use only elementary functions, such as $\sin(x), e^x, \cosh(x),$ etc.

share|improve this question
Unless $a$ and $b$ are allowed to grow with $n$, this is obviously impossible; perhaps you should phrase your limits as being from $1$ to $n$ for concreteness? (i.e., effectively an 'indefinite sum') –  Steven Stadnicki Sep 30 '13 at 15:44
How can evaluating $f(x)$ take time $O(n)$ when $n$ is not a parameter of $f$? –  marty cohen Sep 30 '13 at 16:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.