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?

Weirdly, the preceding text does not define the terms in-degree or out-degree, but intuitively they must represent the count of edges pointing towards or away from the vertex respectively.

In both cases we need to examine each of the \(\lvert V \rvert\) lists for all \(v \in V\). Furthermore, we must proceed to examine each entry in all of these lists. For the out-degree this is obvious because each list with values represents a connection that must be counted. For the in-degree the same reasoning applies as each non-empty list contains one or more connections that must be counted.

So the time to compute either the in-degree or out-degree of every vertex in an adjacency-list representation of a directed graph is

\[O(\lvert E \rvert + \lvert V \rvert)\]