Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

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.

Similarly,

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

share|improve this answer
    
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...) –  Sergey Finsky Nov 21 '12 at 8:42
add comment

Your Answer

 
discard

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

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