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?
How to go from a recurrence relation to a final complexity
algorithms;algorithm analysis;runtime analysis;recursion
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)$.