Q:

A certain algorithm O(|E|log|E|) VS O(|E|log|V|) GRAPHS

Let G = (V,E) be a graph.
Let |V| te number of nodes and |E| the number of edges.
A certain algorithm takes O(|E|log|E|) while another O(|E|log|V|).
Which is more efficient (preferable) in terms of complexity and why?

A:

For general graphs, the algorithm with runtime bound O(|E| log |V|) is preferrable (regarding asymptotic runtime complexity) because |E| <= |V|^2| holds. If n is the number of nodes, the runtime bound of the first algorithm can be expressed as
O(n^2 log n^2)

while the runtime bound of the second one can be expressed as
O(n^2 log n)

which is smaller.

