# How to go from a recurrence relation to a final complexity

I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation.

//Input: Adjacency matrix A[1..n, 1..n]) of an undirected graph G
//Output: 1 (true) if G is complete and 0 (false) otherwise
GraphComplete(A[1..n, 1..n]) {
if ( n = 1 )
return 1 //one-vertex graph is complete by definition
else
if not GraphComplete(A[0..n − 1, 0..n − 1])
return 0
else
for ( j ← 1 to n − 1 ) do
if ( A[n, j] = 0 )
return 0
end
return 1
}


Here is what I believe is a valid and correct recurrence relation:

\qquad \begin{align} T(1) &= 0 \\ T(n) &= T(n-1) + n - 1 \quad \text{for } n \geq 2 \end{align}

The "$n - 1$" is how many times the body of the for loop, specifically the "if A[n,j]=0" check, is executed.

The problem is, where do I go from here? How do I convert the above into something that actually shows what the resulting complexity is?

• Note the edit of the recurrence relation; you may only specify finitely many cases. – Raphael May 20 '12 at 21:57

From what you wrote it seems that for all $k$ you have $T(k)=k-1+T(k-1)$ and $T(1)=0$. Therefore you can get it directly:

$$T(n)=(n-1)+(n-2)+\dots+1+0 = \sum_{k=1}^{n}{(k-1)}=\frac{n(n-1)}{2}$$

So $T(n)$ is in $Θ(n^2)$.

• It is easy to see here, but those $\dots$ need an induction proof in general, and the pattern may be hard to spot. (Just the obligatory pedantic note.) – Raphael May 20 '12 at 22:35

The recursion you have there is this, if we count only matrix accesses:

\qquad \begin{align} T(1) &= 0 \\ T(n) &= T(n-1) + n - 1 \quad \text{for } n \geq 2 \end{align}

Note that it is only an upper bound on the runtime function because the loop is not always executed. It is a linear recurrence relation, and there are many ways of solving those. You can probably unroll $T(n)$, spot a pattern and prove it by induction. This does not always work, though, which is why I want to present a general technique.

This is my favorite way, using generating functions. It uses only mechanical calculation (once you get used to the approach). This is the ansatz:

\qquad \begin{align} \mathcal{T}(z) &= \sum_{n=1}^\infty T(n)z^n \\ &= 0 + \sum_{n=2}^\infty T(n)z^n \\ &= \sum_{n=2}^\infty (T(n-1) + n - 1)z^n \\ &= \sum_{n=2}^\infty T(n-1)z^n + \sum_{n=2}^\infty (n-1)z^n \\ &= z\sum_{n=2}^\infty T(n-1)z^{n-1} + z\sum_{n=2}^\infty (n-1)z^{n-1} \\ &= z\sum_{n=1}^\infty T(n)z^{n} + z\sum_{n=1}^\infty nz^{n} \\ &= z\mathcal{T}(z) + z\cdot\frac{z}{(1-z)^2} \end{align}

For the identity needed for the last step, see the TCS Cheat Sheet. If we now solve this equation for $\mathcal{T}$, we get:

\qquad \displaystyle \begin{align} \mathcal{T}(z) &= \frac{z^2}{(1-z)^3} \\ &= z^2\sum_{n=0}^\infty \binom{n+2}{n}z^n \\ &= \sum_{n=0}^\infty \frac{(n+2)(n+1)}{2}z^{n+2} \\ &= \sum_{n=2}^\infty \frac{n(n-1)}{2}z^{n} \\ &= \sum_{n=1}^\infty \frac{n(n-1)}{2}z^{n} \\ \end{align}

For the first step, see again the Cheat Sheet. Remember that we started with $\mathcal{T}(z) = \sum_{n=1}^\infty T(n)z^n$ so we can read the solution off the last line:

$\qquad \displaystyle T(n) = \frac{n(n-1)}{2} \in \Theta(n^2)$

• Thank you very much for that cheat sheet. Going to pass that around to everyone in my class. – Chris Bond May 20 '12 at 23:11
• Sledgehammer, meet mosquito. – JeffE May 21 '12 at 8:42
• @JeffE: Learn how to use the sledgehammer before you really need it. (Btw, if you leave out all the small steps I included for the sake of clarity, this approach is often not (much) longer than others, provided you do them rigorously.) – Raphael May 21 '12 at 8:53
• @Raphael: I have never needed generating functions. – JeffE May 21 '12 at 9:24
• @JeffE: I am sure you have used other rigorous machinery then. I know I have seen analyses I don't know how to perform without them. – Raphael May 21 '12 at 11:05