Both are O(m + n)
where m
is the number of edges and n
is the number of vertices.
Start a set of counters, one for each vertex, one for in-degree and out for out-degree.
Scan the edges. For the out vertex of each edge, add one to the out-degree counter for that vertex. For the in vertex of each edge, add one to the in-degree counter for that vertex. This is O(m)
operation.
Output the out-degree and in-degree counters for each vertex, which is O(n)
.
That's how you get O(m + n)
.