Complexity and graph bounds An algorithm runs in Θ(|V|·|E|). What is the resulting running time on a SPARSE graph, where |E| = Θ(|V|), and on a DENSE one, where |E| = Θ(|V|²)?

Question

Accepted Answer

Θ(|V|²) on the sparse graph and Θ(|V|³) on the dense one.

Answer

Θ(|V|) on the sparse graph and Θ(|V|²) on the dense one.

Answer

Θ(|V| log |V|) on the sparse graph and Θ(|V|³) on the dense one.

Answer

Θ(|V|²) on both.

Answer

Θ(|V|²) on the sparse graph and Θ(|V|⁴) on the dense one.

Crowdly

Complexity and graph bounds An algorithm runs in Θ(|V|·|E|). What is the resulti...

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