Answer: ( \frac{2E}{V}) avg number of degree.
If you have V, no self loop, no parallel edges, what is maximum edges?
Answer: ( \frac{V(V-1)}{2} )
So if you have (V), considered sparse.
Adjacency lists represent each edge twice, so the number of spaces taken (number of nodes) is (2E). So the full space used by this is (V + 2E), so our space complexity is O(E + V).
- (V - 1)
Depth-first search trace on whiteboard:
Count) worst case runtime.
Back to the analysis of the algorithm:
Worst case space is from a linear graph:
