What is the performance behavior of a linked adjacency list for determining whether an edge exists between two vertices? A) constant time B) O( N ²) where N is the number of vertices C) linear with the length of the list D) logarithmic with the total number of vertices

Question

Quizplus · Accepted Answer

In a linked adjacency list, edges from a vertex are stored in a linked list, so determining whether an edge exists between two vertices requires searching through the linked list of one vertex to see if the other vertex is listed. Therefore, the performance behavior for determining whether an edge exists between two vertices is linear with the length of the linked list.

What Is the Performance Behavior of a Linked Adjacency List