Is O(|V| * k) equal to O(|E|)?

Question

I assume that when representing adjacency lists, we need to iterate over all the vertices and their neighbors, so the time complexity to build an adjacency list is O(|V| * k) where V is the set of vertices and k is the number of neighbors a certain vertex has (k = |V| - 1 if the graph is complete). However, every resource I've encountered states that the time complexity to build an adjacency list is O(|E|) where E is the set of edges.

Since we are considering the worst case, the worst case of a graph is a connected one, where |E| is equal to (|V| 2) = (|V| * (|V|-1))/2. As mentioned above, building an adjacency list from a complete graph requires iterating over all the vertices and their neighbors. The time complexity of this operation will be |V| * k where k is |V|-1. So, it should be O(|V| * (|V|-1)) => O(|V|^2). Since we found that the number of edges is (V * (V-1)) / 2 => O(|V|^2), then the two complexities, O(|V| * k) and O(|E|) should be the same.

The thing that confuses me is why people prefer to use O(|E|) instead of O(|V| * k)?

user_2411243 · Answer

Is O(|V| * k) equal to O(|E|)?

Yes.

where V is the set of vertices and k is the number of neighbors a certain vertex has

This definition is incorrect since k depends on "the certain vertex"` so you would need to define it as the max-degree (maximal number of edges a vertex has) in order to have a usable definition.

On the note of max-degree, O(maxdeg * |V|) is not equals to O(|E|). The max-degree is a worse approximation of the complexity than |E|.

Just imagine a graph with a single vertex that has 1_000 edges but every other vertex only has 1 edge.

But since Big-O only defines upper-bounds, the algorithm is of course still in O(maxdeg * |V|).

In any case, you will maximally look once at each edge in the graph, so |E|. And the amount of edges is the sum of all outgoing edges of all vertices, i.e. what you tried to formulate with |V| * k. So both are absolutely identical. I.e.

|E| = sum (v * outdegree(v))

(k is not the maxdegree in this case but the outdegree specific to each v)

The thing that confuses me is why people prefer to use O(|E|) instead of O(|V| * k)?

In general, it is just much more common to view a graph as an entity that has vertices and edges, with operations being dependent on V and E. It is much simpler to just say O(|E|) than to overcomplicate things by looking at it from an "vertices and their outgoing edges"-angle.

Is O(|V| * k) equal to O(|E|)?

1 Answers