HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What does $|V|=O(|E|)$ mean?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
doesmeanwhat

Problem

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it says that $O(|V|\log|V|+|E|\log|V|) = O(|E|\log|V|)$, because $|V|=O(|E|)$. What does $|V|=O(|E|)$ mean and why is it so?

Solution

First, $|V|$ is the number of vertices and $|E|$ is the number of edges.

The point is that if a graph is connected it must have at least $|V|-1$ edges. Therefore, $|V|\leq |E|+1$, so
$$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$

Writing $|V|=O(|E|)$ is something of an abuse of notation. $O(\cdot)$ is an asymptotic statement about what happens as some variable becomes large, over some infinite family of instances. So, here, we're supposed to imagine that the infinite family of instances is the set of all connected finite graphs. It would have been clearer to just write $|V|\leq |E|+1$.

Context

StackExchange Computer Science Q#112533, answer score: 3

Revisions (0)

No revisions yet.