Let $a_n$ represent the number of directed acyclic graphs on $n$ vertices. Then the wikipedia, gives me the following recurrence:
$$a_n = \sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}2^{k(n-k)}a_{n-k}$$
I want an upper-bound on the computational complexity of this function in big O notation. I thought that it would be polynomial in $n$, but my analysis attempt says otherwise.
My attempt: Let $T(n)$ be the time required for computing $a_n$, assuming cost of multiplication and binomial coefficient evaluation to be constant. We have that: $$T(n) = \sum_{k=1}^{n}T(n-k)$$ Let $T(0) = c$. Now the question reduces to, what is $\sum_{k=0}^{n} T(n)$ ?
Your attempt is wrong because you can store the $a_k$ and only need to compute them once, not again in each step. The number of binomial coefficients, multiplications and additions you need to compute for $a_n$ is linear in $n$, and the total cost is the sum of those linear costs from $1$ to $n$, which is quadratic in $n$.