Complexity and graph bounds A graph with |V| vertices and |E| edges is stored once as an adjacency matrix and once as an adjacency list. How much space does each use?

Question

Accepted Answer

Θ(|V|²) for the matrix and Θ(|V| + |E|) for the list.

Answer

Θ(|E|) for the matrix and Θ(|V|) for the list.

Answer

Θ(|V|·|E|) for the matrix and Θ(|E|) for the list.

Answer

Θ(|V| + |E|) for both.

Answer

Θ(|V|²) for both, since both have to be able to represent every possible edge.

Crowdly

Complexity and graph bounds A graph with |V| vertices and |E| edges is stored on...

Want instant access to all verified answers on learning.monash.edu?