Problem Detail: 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?
Asked By : Chris Bond
Answered By : jmad
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)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1959
