Running time and stack depth of a lisp recurrence

Question

Consider the following sequence $a_n$:

\begin{align*} a_0 &= \alpha \\ a_k &= \beta a_{k-1} + \kappa \end{align*}

Now consider the implementation of this sequence via lisp:

(defun an (k)
  (if (= k 0) alpha
    (+ (* beta (an (- k 1))) kappa)))

What is the running time to compute (an k) just as it is written? Also, what would be the maximum stack depth reached? My hypothesis would be that both the running time and stack depth are $O(k)$ because it takes $k$ recursive calls to get to the base case and there is one call per step and one stack push per step.\ .

Is this analysis corect?

Answer 1

The time and other resources (such as stack consumption) needed to run an with the argument $x \in \mathbb{N}^*$ is the sum of:

• the resources needed to compute (- k 1) with k bound to $x$;
• the resources needed to compute an with the argument $x-1$;
• the resources needed to compute (if (= k 0) alpha (+ (* beta $y$`) kappa))` where $y$ is the value returned by the recursive call to an.

Let $T(x)$ be the running time of this computation. For $x \gt 0$, by the analysis above, $T(x) = T(x-1) + C$ for some constant $C$ (assuming that the arithmetic operations take constant time). A very simple induction shows that $T(x) = C \, x + T(0)$, i.e. $T(x) = \Theta(x)$. The same goes for stack consumption.

There is more than one stack push per recursive call, (3 in a naive interpreted Lisp such as Emacs Lisp), but that doesn't affect the $O$ or $\Theta$ analysis. Other than this minor detail your analysis is correct.

Are you sure that you typed the right code? Emacs has a fairly low limit on stack usage but even it can sustain more recursive calls (up to 123 in Emacs 23 where max-lisp-eval-depth is 500).