AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Easygraphrepresentation

~60s

Space of an adjacency list

A graph has V vertices and E edges. How much space does its adjacency list representation take?

Show the answer and the worked solution

Correct answer: C.

O(V + E)

Worked solution

  1. The representation keeps one list header per vertex, which costs O(V) even for isolated vertices.
  2. Every edge contributes one list node in a directed graph, or one in each endpoint's list in an undirected graph, which costs O(E).
  3. Adding the two gives O(V + E), which beats the O(V²) adjacency matrix whenever the graph is sparse.

Answer: O(V + E).

The idea

Adjacency lists win on sparse graphs and on iterating a vertex's neighbours; adjacency matrices win when you must answer 'is there an edge from u to v?' in constant time.

Shortcut. One header per vertex plus one node per edge end: isolated vertices still need their headers and dense graphs still need their nodes, so neither term can be dropped.

Common trap. "O(E)" counts only the list nodes and forgets the V headers, which dominate when the graph has few edges.

Data Structures & Algorithms

34 of 40

Level

Easy

Target time

~60s

PreviousNext
AI InterviewGet started

Space of an adjacency list — Aptitude Question

Space of an adjacency list: A graph has V vertices and E edges. How much space does its adjacency list… Answer and worked solution on CodeKairo.

Question

A graph has V vertices and E edges. How much space does its adjacency list representation take?

Options

  1. O(E)
  2. O(V)
  3. O(V + E)
  4. O(V²)
Show the answer and the worked solution

Correct answer: C. O(V + E)

Worked solution

  1. The representation keeps one list header per vertex, which costs O(V) even for isolated vertices.
  2. Every edge contributes one list node in a directed graph, or one in each endpoint's list in an undirected graph, which costs O(E).
  3. Adding the two gives O(V + E), which beats the O(V²) adjacency matrix whenever the graph is sparse.

Answer: O(V + E).

The idea

Adjacency lists win on sparse graphs and on iterating a vertex's neighbours; adjacency matrices win when you must answer 'is there an edge from u to v?' in constant time.

Shortcut. One header per vertex plus one node per edge end: isolated vertices still need their headers and dense graphs still need their nodes, so neither term can be dropped.

Common trap. "O(E)" counts only the list nodes and forgets the V headers, which dominate when the graph has few edges.

All Data Structures & Algorithms questions · placement mock tests