Consider the following algorithm to check whether a graph defined by its adjacency matrix is complete.
ALGORITHM GraphComplete(A[0..n-1, 0..n-1])
// INPUT: Adjancency matrix A[0..n-1, 0..n-1] of an undirected graph G
// OUTPUT: 1 (true) if G is complete and 0 (false) otherwise
if n=1 return 1 // one-vertex graph is complete by definition
else
if not GraphComplete(A[0..n-2, 0..n-2]) return 0
else for <-- 0 to n-2 do
if A[n-1, j] = 0 return 0
return 1
What is the algorithm's efficiency class in the worst case?