Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some recurrence relationships I use to compute some coefficients of a series. I want to know what the time complexity of computing these is. Suppose I know the coefficients $a_0,...,a_n$, and I want to compute $c_0,...,c_n$ as follows

$ c_{n}=\begin{cases} e^{b_{0}}, & n=0\\ \frac{1}{n}\sum_{k=1}^{n}kb_{k}c_{n-k}, & n\geq1 \end{cases}$


$b_{n}=\begin{cases} \frac{1}{a_{0}}, & n=0\\ -\frac{1}{a_{0}}\sum_{i=1}^{n}a_{i}b_{n-i}, & n\geq1 \end{cases}$

So far this is what I have. If we know $b_0,...,b_{k-1}$ then $b_k$ can be computed in $O(k)$ time, so to compute $b_0,...,b_{n}$ takes $\sum_{k=0}^{n}O(k)=O(n^2)$ time.

Now suppose that we know $b_0,...,b_{k}$ and $c_0,...,c_{k-1}$ then it takes $O(k)$ time to compute $c_k$. Thus to compute $c_0,...,c_{n}$ it takes $\sum_{k=0}^{n}O(k)=O(n^2)$. Ofcourse we have to take into account the time it takes to compute $b_0,...,b_{n}$ which is $O(n^2)$.

So can I conclude that the time it takes to compute $c_0,...,c_{n}$ is


share|cite|improve this question
What is your cost model? Yuval applies the logarithmic cost model, but there are others. – Raphael Jan 28 '13 at 10:15
@Raphael I am not too familiar with cost models, but I was assuming all simple operations (addition, multiplication etc. even exponentiating, $e^{b_0}$, since I only need to do this once) take the same amount of time i.e. uniform cost model – mark Jan 28 '13 at 23:39
up vote 2 down vote accepted

You also need to take into account the size of the coefficients. Adding integer coefficients of bit-length $\ell$ takes time $O(\ell)$, and multiplying them takes time $\tilde{O}(\ell)$, i.e. $O(\ell (\log \ell)^k)$ for some $k$ (any $k > 1$ will do). Your case is slightly more complicated, since the answer is rational and uses the "indefinite" value $e^{1/a_0}$, so in general it is going to be a polynomial in $e^{1/a_0}$ with rational coefficients. This further increases the running time.

share|cite|improve this answer

Your Answer


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.