21 views
Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex ? How long does it take to compute the in-degrees ?
| 21 views

To compute the out degree each vertex we would need $O(V+E)$.
To compute the in degree we have to scan through adjacency lists and count how many times each vertex has appeared. This is $O(V+E)$