Complexity and graph bounds On a simple directed graph with |V| vertices and |E| edges, which of these statements is true?

Question

Accepted Answer

|V|·|E| is O(|V|³), because a simple directed graph has at most |V|(|V| − 1) edges.

Answer

|V|·|E| grows faster than |V|³ on sparse graphs and slower on dense ones.

Answer

|V|³ is O(|V|·|E|), because a connected graph has at least |V| − 1 edges.

Answer

Neither can be compared without knowing the constant factors.

Answer

|V|·|E| and |V|³ are always the same order.

Crowdly