LIVE Course for free

Rated by 1 million+ students
Get app now
0 votes
in Computer by (71.8k points)

In an adjacency list representation of an undirected simple graph G = (V, E ), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E | = m and |V | = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list? 

(A) Θ (n2)

(B) Θ + (n m) 

(C) Θ(m2

(D) Θ(n4)

Please log in or register to answer this question.

1 Answer

+1 vote
by (70.8k points)

Correct option is (B) Θ + (n m)

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.