I know an O(n * sqrt(n)) approach, but I don't know its proof. I think proving it is difficult, so just take it as magic :)

Let P(n) = number of partitions of n.

Then, P(n) = P(N — 1) + P(N — 2) — P(N — 5) — P(N — 7) + ...

The k-th term of sum in absolute value is P(N — x[k]). The signs of sum's terms alternate from 2 to 2, so they are ++--++--++-- and so on. By x[k] I noted k-th pentagonal number . By formula of pentagonal numbers it's easy to see that when calculating P(n) you add about sqrt(n) numbers (because there are about sqrt(n) pentagonal numbers <= n) so complexity is O(n * sqrt(n)).