Big O Complexity for Graphs: Adjacency Matrix vs Adjacency List

Graphs can be represented in two main ways: Adjacency Matrix and Adjacency List. Each method has its own pros and cons depending on how much memory it needs and how quickly it can handle different operations.

1. Space Complexity

Adjacency Matrix : O(V^2)
Adjacency List : O(V+E)

• V: Number of vertices.
• E: Number of edges.
• Adjacency Matrix requires a V×V grid, making it less efficient for sparse graphs.
• Adjacency List only stores edges for each vertex, making it space-efficient for sparse graphs.

2. Time Complexity: Adding a Vertex

Adjacency Matrix : O(V^2)
Adjacency List : O(1)

• Adjacency Matrix: Adding a vertex may require creating a new 𝑉+1×𝑉+1 matrix and copying the old matrix, which is expensive.
• Adjacency List: Simply add a new empty list for the new vertex, which is constant time.

3. Time Complexity: Adding an Edge

Adjacency Matrix : O(1)
Adjacency List : O(1)

Both representations allow constant-time edge additions:

• Matrix: Set the matrix cell to 1 (or edge weight).
• List: Append the edge to the list.

4. Time Complexity: Removing an Edge

Adjacency Matrix : O(1)
Adjacency List : O(E/V)

• Adjacency Matrix: Directly unset the cell, which is constant time.
• Adjacency List: Requires searching through the list for the edge, leading to O(E/V) time on average.

5. Time Complexity: Removing a Vertex

Adjacency Matrix : O(V^2)
Adjacency List : O(V+E)

• Adjacency Matrix: Removing a vertex involves deleting its row and column, which can require shifting elements in the matrix.
• Adjacency List: Removing a vertex requires deleting the list for the vertex and traversing all other lists to remove edges to the vertex.

Choosing the Right Representation

• Adjacency Matrix:
  Suitable for dense graphs where E≈V2.
  Offers constant-time edge operations but consumes more space.

• Adjacency List:
  Ideal for sparse graphs where E≪V2.
  Space-efficient and generally faster for operations involving vertices.