Finding recurrence relation for running time of an algorithm

Question

I am pretty new to this, consider the following algorithm:

Calc_a(n):
    if n ==1: return 1
    else:
    sum = 0
    for i=1 to n-1:
        sum = sum + calc_a(i)
    return sum

So after running this algorithm a few times I see it basically finds the n'th element in a sequence defined by this recurrence relation:

$a_n = \sum_{i=1}^{n-1}a_i $

I need to find the recurrence relation for this algorithm running time per input. Walk me through it :)

Lets define running time as $T(n)$.
So the base case n=1 is $O(1)$ (theta?), as we just return 1.
Then we iterate (n-1) times , each time performing addition and calling the function on the current index, this is where I get confused.
I know how to deal with loops and recursion individually, not together.

My homework specifies that I should use constants rather than asymptotic notations. Does that means I should define the running time of Calc_a(i) as some constant?

How should I go about this?

*** EDIT ****
The answer I've come up with:

$ T(n) = \begin{cases} 1, & \text{if $n = 1$} \\ \sum_{i=1}^{n-1}( T(i) + B) & \text{else} \end{cases} $

For some constant B.

Answer 1

For starters, there are a few ways to prove recursive complexity. Some helpful notes can be found all over. For this problem, we can think about the recursion tree. The root of the tree is the Calc_a(n) call, and it's children are all $n-1$ nodes for each Calc_a(i) call initiated by the original Calc_a(n) call. For each of it's children, we can define the subtree rooted at them in the same manner. Our first step will be to determine how many nodes are in this tree.

Lets for some call Calc_a(n), lets see how many times Calc_a(i) is called for some $i<n$. This is the same as counting all Calc_a(i) nodes in the tree defined above. Let's first notice a pattern.

• Calc_a(n-1) is only called once, that is clear.
• Calc_a(n-2) will be called by the original Calc_a(n) call as well as the Calc_a(n-1). 2 calls
• What about Calc_a(n-3)? Well we have 1 from the original call, and we can see that there will be two calls from Calc_a(n-1), and one more from Calc_a(n-2) 4 calls
  • Why are there two calls from Calc_a(i-1)? Well, in the previous bullet point we see that for any $i$, Calc_a(i-2) will be called twice for every Calc_a(n). We can use that logic here.
• Calc_a(n-4)? We have one from the original call. As we can see in the previous bullet point, there will be 4 resulting calls to Calc_a(n-4) from Calc_a(n-1), 2 from Calc_a(n-2), and 1 more from Calc_a(n-3) 8 calls
  • Again we use the fact that the previous bullet point showed that there are 4 resulting calls to Calc_a(i-3) from any Calc_a(i) call.

We notice the pattern unfold that any Calc_a(i) is called twice as many times as Calc_a(i+1). Therefore Calc_a(i) is called $2^{n-i-1}$ times.

$$\sum_{i=1}^{n-1}2^{n-i-1}=\sum_{i=0}^{n-2}2^{i}=2^{n-1}$$ (I'm not sure if you're expected to include the original Calc_a(n) call, if you are, just add 1)

Proof Method 1

Now, as far as $T(n)$ goes, we can define it as $T(n)=f(n)+\sum_{i=1}^{n-1}T(i)$ where $f(n)$ is the work done in the function not including the recursive calls. As I'm sure you can tell, this is just a constant, so each node in the work tree does constant work. So we've determined the number of nodes in the tree. This means that the total work of the tree is simply $T(n)\approxeq 2^{n-1}$ or $T(n)=\theta(2^{n-1})$.

You may be wondering why the sum doesn't contribute to the complexity. Well, we could look at the loop and include the sum, then $T(n)=f(n)+\sum_{i=1}^{n-1}(g(i) + T(i))$ where $g(i)$ is the complexity of computing the sum from $T(i)$. However, we can just consider $g(i)$ as a constant as well, since most arithmetic operations can be theoretically considered constant time (this is definitely not always the case, but that is a whole nother topic). Because the constant complexity of the addition is dominated by the complexity of the accompanying $T(i)$ call, we arrive at the same complexity.

Proof Method 2

A more formal method of proving this, and one that may be required (from my experience) on an exam or homework, is to use induction. Generally, the Method 1 above is useful for getting a guess on the complexity. Once you have a good guess, you use induction to prove it, as suggested in the comments below.

Claim: $T(n)=\theta(2^{n-1})$

Base case: $T(1)=1$ (we can also see that $T(2)=2$ and $T(3)=4$) (Notice we are counting the number of calls to Calc_a()

Inductive step \begin{align*} T(n+1) & = f(n+1) + \sum_{i=1}^n ( g(i) + T(i)) \\ & = f(n+1) + \sum_{i=1}^{n-1} (g(i) + T(i)) + (T(n) + g(n)) \\ & = f(n+1) + T(n) - f(n)+ T(n) + g(n)\\ & = 2T(n) + g(n) \\ & \leq 2^n+c \quad \text{for some } c\geq g(n) \end{align*} Where the last line follows from the inductive hypothesis and the fact that $g(n)$ is a constant i.e. $g(n)=O(1)$.

Answer 2

One general way to solve recurrences is to use generating functions. A good reference is Wilf's "generatingfunctionology". Define the generating function:

$\begin{equation*} A(z) = \sum_{n \ge 0} a_{n + 1} z^n \end{equation*}$

Write your recurrence with no index subtractions, multiply by $z^n$, sum over $n \ge 0$, recognize some sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= \sum_{n \ge 0} z^n \sum_{0 \le k \le n} a_{k + 1} \\ \frac{A(z) - a_1}{z} &= \frac{A(z)}{1 - z} \end{align*}$

The last is because:

$\begin{align*} \sum_{n \ge 0} z^n \sum_{0 \le k \le n} a_{k + 1} &= \left( \sum_{n \ge 0} z^n \right) \cdot \left( \sum_{n \ge 0} a_n z^n \right) \\ &= \frac{1}{1 - z} \cdot A(z) \end{align*}$

OK, now we have an equation for $A(z)$, solve that one, using $a_1 = 1$.

$\begin{equation*} A(z) = \dfrac{1}{2} + \dfrac{1}{2} \cdot \dfrac{1}{1 - 2 z} \end{equation*}$

This is a constant term and a geometric series, using Iverson's bracket ($[\mathit{condition}]$ is 1 if the $\mathit{condition}$ is true, 0 otherwise), the coefficient of $z^n$ is:

$\begin{align*} a_{n + 1} &= \dfrac{[n = 0] + 2^n}{2} \\ a_n = 2^{n - 2} + \dfrac{1}{2} [n = 1] \end{align*}$

Answer 3

You have already found the recurrence relation which, slightly corrected, yields $$ a_n \leq \sum_{i=1}^{n-1} (a_i + B) + C. $$ Let's solve instead what you wrote, $$ a_n = \sum_{i=1}^{n-1} a_i. $$ In order to solve this, let $b_n = \sum_{i=1}^n a_i$. Then $$ b_n = a_n + \sum_{i=1}^{n-1} a_i = 2\sum_{i=1}^{n-1} a_i = 2b_{n-1}. $$ Therefore $b_n = 2^n A$ for some constant $A$ Finally, $$ a_n = b_n - b_{n-1} = 2^{n-1} A. $$