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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm for computing $n^k$ in $O(\lg k)$ and it's overall time is $O(n \lg k)$, the other, using Bernoulli numbers, can be implemented in $O(k^2)$. And the most complicated works in $O(n \lg \lg n + n \lg k / \lg n)$ - it uses somewhat like sieve of Eratosthenes. (Don't know if it's well-known, I came up with this by myself, so if it not well-known, I can explain how to do it)

Every of this 3 algorithms, but the first, has it's own pros and cons, for example for every $k = n^{O(1)}$ the last algorithm works in $O(n \lg \lg n)$ time, while first in runs $O(n \lg n)$ and second is even worse. When $k = o(\sqrt{n \lg \lg n})$ second algorithm performs better than others.

So my question is: if there exists some more efficient algorithms? (Like in previous problems, I am not merely interested in asymptotics in $n$, but in $k$ too)

Thank you very much!

P.S. : I've asked this question in cstheory forum, but, maybe, it's more appropriate place for it.

share|cite|improve this question
You don't explain what you want to do very clearly. You want to evaluate power sum polynomials? How many terms has the power sum, in what kind of values are you evaluating? Or do you want to express power sum polynomials in some other basis of symmetric functions? Which one? The $n$ in $n^k$ is it different from the one in $O(n\lg k)$? – Marc van Leeuwen Nov 17 '12 at 17:12
Sorry, really, there is a misunderstanding in terminology. – Sergey Finsky Nov 17 '12 at 19:41

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.