A vertex v in an undirected graph G is called a celebrity if v has an edge to ev
ID: 3710673 • Letter: A
Question
A vertex v in an undirected graph G is called a celebrity if v has an edge to every other vertex in G. Consider this algorithm for finding a celebrity, if one exists. The input for the algorithm is an n x n adjacency matrix representing G. (Remember there are no self loops in an undirected graph.)
FINDCELEBRITY(M):
n = M.size
for i = 1,2,........n:
edges = 0
for j = 1,2,........,n:
if M[i][j] = 1: #count only this operation only
edges = edges + 1
if edges = n -1:
return i
return NIL
In this question, you will analyse the time complexity of algorithm FINDCELEBRITY by counting only the number of accesses to the adjacency matrix (ignoring all other operations). Q: Compute the average-case number of accesses performed by FINDCELEBRITY on the random input graph specified above. Do not simplify your expression
Explanation / Answer
Solution:
In the above-given algorithm, the adjacency list is represented by M[i][j].
In the average case as well it will be n^2.
Timen complexity= O(n^2)
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)