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!


1 Answer 1


Here's another approach, which I think runs in $O(k)$ time.

Define $S_k$ by

$$S_k = {1 \choose k} + {2 \choose k} + \dots + {n \choose k} = {n+1 \choose k+1}.$$

The right-hand-side can be computed in $O(k)$ time.


$$S_{k-1} = {1 \choose k-1} + {2 \choose k-1} + \dots + {n \choose k-1} = {n+1 \choose k},$$

and given the value of the previous sum $S_k$, we can compute this sum $S_{k-1}$ in $O(1)$ time (using the fact that ${n+1 \choose k} = {n+1 \choose k+1} \times {k+1 \over n-k+1}$).

In this way, we can compute all of the sums $S_k,\dots,S_2,S_1,S_0$ in $O(k)$ time.

Furthermore, we can find constants $c_0,\dots,c_k$ such that

$$x^k = c_k {x \choose k} + \dots + c_1 {x \choose 1} + c_0 {x \choose 0}$$

holds for all $x$. It follows that

$$S = 1^k + 2^k + \dots + n^k = c_k S_k + \dots + c_1 S_1 + c_0 S_0,$$

which can be computed in $O(k)$ time.

  • $\begingroup$ Wow! But how can you compute $c_k$ in $O(k)$ time? I know how to do it in $O(k^2)$ (2 algorithms), the first is to exploit solving triangular system (just plug in the equation $0$, $1$, ..., $k$, this system is triangular). And the second is that coefficients of this representation are Stirling numbers of second kind, and there is a recurrence for them similar to the recurrence of binomial coefficients, which help them to be computed in $O(k^2)$. (Sure there is scheme, described by you, which can compute binomial coeff. in $O(k)$, but I wonder if there exists similar to Stirling numbers...) $\endgroup$
    – user197284
    Nov 21, 2012 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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