5

I am reading "Algorithms Design" By Eva Tardos and in chapter 3 it is mentioned that adjacency matrix has the complexity of O(n^2) while adjacency list has O(m+n) where m is the total number of edges and n is the total number of nodes. It says that in-case of adjacency list we will need only lists of size m for each node.

Won't we end up with something similar to matrix in case of adjacency list as we have lists,which are also 1D arrays. So basically it is O(m*n) according to me. Please guide me.

1 Answer 1

9

An adjacency matrix keeps a value (1/0) for every pair of nodes, whether the edge exists or not, so it requires n*n space.

An adjacency list only contains existing edges, so its length is at most the number of edges (or the number of nodes in case there are fewer edges than nodes).

It says that in-case of adjacency list we will need only lists of size m for each node.

I think you misunderstood that part. An adjacency list does not hold a list of size m for every node, since m is the number of edges overall.

In a fully connected graph, there is an edge between every pair of nodes so both adjacency list and matrix will require n*n of space, but for every other case - an adjacency list will be smaller.

3
  • All this is only about how much space the data structures used to represent the graph need (which is what Rajat seems to ask for). We often also want to be able to perform certain operations on the graph (e.g. edge insertion/deleten/existence check), and the two structures offer different time complexities for some of them, which is something to keep in mind.
    – G. Bach
    Commented Sep 16, 2015 at 13:09
  • Should "fully connected graph" actually be "complete graph" in this answer? Commented Apr 29, 2020 at 3:43
  • @MarkusAmaltheaMagnuson Yes, a graph with all edges present...
    – Armaan
    Commented Jun 4, 2020 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.