6
$\begingroup$

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?

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

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)$.

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael May 20 '12 at 22:35
6
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ Thank you very much for that cheat sheet. Going to pass that around to everyone in my class. $\endgroup$ – Chris Bond May 20 '12 at 23:11
  • 6
    $\begingroup$ Sledgehammer, meet mosquito. $\endgroup$ – JeffE May 21 '12 at 8:42
  • $\begingroup$ @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.) $\endgroup$ – Raphael May 21 '12 at 8:53
  • 3
    $\begingroup$ @Raphael: I have never needed generating functions. $\endgroup$ – JeffE May 21 '12 at 9:24
  • $\begingroup$ @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. $\endgroup$ – Raphael May 21 '12 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.