patternMinor
What does $|V|=O(|E|)$ mean?
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$.
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.