What is the complexity of generating bell numbers?

Question

I want to know the complexity of generating the bell numbers and also want to know the nature of this problem (NP-complete, NP-hard, etc).

Answer 1

By the "triangle scheme", very similar to Pascal's triangle, you compute the $n^{th}$ row from the $(n-1)^{th}$ with $n$ additions so this method involves $O(n^2)$ additions.

As there are $n$ numbers to generate, and the asymptotic value of the logarithm (i.e. the number of digits; see https://en.wikipedia.org/wiki/Bell_number#Growth_rate) is $\Theta(n\log n)$, the trivial lower bound of the complexity is $\Omega(n^2\log n)$. And by the previous argument, an upper bound is $O(n^3\log n)$.

---

This site http://fredrikj.net/blog/2015/08/computing-bell-numbers/ is much advanced on the topic and reports computation of the $n^{th}$ number to be doable in $n^{2+o(1)}$, and the same bound for the computation of the $n$ first numbers.

This is not compatible with my $\Omega(n^2\log n)$ lower bound.