Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 5 / c

With an adjacency list, initialization and the outer loop cost $O(|V|)$. Each vertex is visited once, and the adjacency scans inspect each edge of a graph twice, once from each endpoint. The total worst-case time is therefore $O(|V|+|E|)$, with $O(|V|)$ labels and recursion-stack space. An adjacency matrix representation instead incurs $O(|V{|}^2)$ scanning time.