# What are some examples of difficult sums?

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

$$\sum_a^{a+n}{f(x)}$$

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

NOTE

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

-
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