Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 1

Problem:

Given an adjacency-list representation of a directed graph, where each vertex maintains an array of its outgoing edges (but *not* its incoming edges), how long does it take, in the worst case, to compute the in-degree of a given vertex? As usual, we use $ n $ and $ m $ to denote the number of vertices and edges, respectively, of the given graph. Also, let $ k $ denote the maximum in-degree of a vertex. (Recall that the in-degree of a vertex is the number of edges that enter it.)
Solution:

One must read all edges (or the edge not read may contribute to a in-degree count of the given vertex), so we have the time lowered bounded by $ m $.

On can compute the in-degree by just reading all edges and keep track of the in-degree count, so we have the time upper bounded by $ m $.

Therefore the solution is $ \theta(m) $.