CODEWITHSUNDEEP
algorithmgraph-algorithm
Chieve
Chieve

Reputation: 59

What is the order of efficiency of an Adjacency list

Is it O(n+m) or O(nm)? To construct it be O(nm) and if we wanted to search, add, or delete a value it will be O(n+m), right? Is there anything else that would be important to consider?

Also to convert a matrix into a list it takes O(n2) and to turn a list into a matrix it is only O(nm) correct?

Upvotes: 1

Views: 802

Answers (2)

Lucas Sampaio
Lucas Sampaio

Reputation: 316

  • The cost to build an adjacency list is O(m) from zero (because we can add any edge in O(1)) and O(n²) from an adjacency matrix (because we have to check every cell of the matrix).
  • Adding an edge u-v is O(1) because we can append an entry v to the end of the adjacency list of vertex u
  • Removing an edge u-v takes O(n) operations because we have to scan the adjacency list of vertex u in order to find the entry for v before we can remove it.
  • Finding if there is an edge u-v also takes O(n) steps because we must scan the adjacency list of vertex u and check if there is an entry for v

Remotion and search can me improved to O(logN) or average O(1) using a BST or hashing instead of a linked list to store the adjacencies, but most graph algorithms require us to scan the whole adjacency list of a vertex instead of checking individual entries, so we can usually work well with linked lists.

We can convert an adjacency list to an adjacency matrix in O(m), assuming the matrix is initially filled with zeroes. All we have to do is scan the adjacency list of every vertex, and for each edge U-V with weight W we can do matrix[U][V] = W (or matrix[U][V] = 1 if the graph is not weighted). Since we are looking to each edge exactly once (or twice if the graph is not directed), the complexity os O(m).

Upvotes: 1

yd1
yd1

Reputation: 277

i think that when you convert the list to the matrix you go:

for each vertex `O(n)`
    for each neighbour `O(n)`

and that's why its also O(n^2).

if m>n, one vertex cannot have all m neighbors, and that's why you avoid O(n^3)

exemple:

a: b, c, d

b: a, c, d

c: a, b, d

d: a, b, c

full graph: O(n^2) list size. although n = 4 and m = 6, the size is 4x4 and not 4x6.

(m = (4 * (4-1))/2 = 6 = O(n^2) --full graph formula)

Upvotes: 0

Related Questions