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?