Menu
Why DFS algorithm is having O(V2) compelxity in adjacency matrix representation and O(V+E) in adjacency list representations.
456
dfs() has a time complexity of O(8^(n^2)). (n ^ 2) is the total number of characters present in the matrix.
The adjacency matrix takes Θ(n 2 ) space, whereas the adjacency list takes Θ(m + n) space. The adjacency matrix takes Θ(n) operations to enumerate the neighbours of a vertex v since it must iterate across an entire row of the matrix. The adjacency list takes deg(v) time.
Thus, the time complexity is O(|E|). In order to find for an existing edge the content of matrix needs to be checked. Given two vertices say i and j matrix[i][j] can be checked in O(1) time. In an adjacency list every vertex is associated with a list of adjacent vertices.
For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E(total number of edges). So, the complexity of DFS is O(V + E). Show activity on this post. It's O(V+E) because each visit to v of V must visit each e of E where |e| <= V-1.
For matrix:
There is one row and one column for each vertex. Position i,j contains 1 if there is an edge from vertex i to vertex j.
The size of the whole matrix is |V|^2
Why the complexity is |V|^2?
Because each position in the matrix is visited once.
For adjacency linked list:
Collection of linked lists with one list for each vertex such that the list for vertex v is the list of all vertices adjacent to vertex v.
Why the complexity is |E|+|V|? Because each position in the adjacency linked list is visited once and there are |V| vertices and |E| edges.
58
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
