1
$\begingroup$

I'm not sure I understand the answer to this question:

Question 9.

What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, where $V$ is the number of vertices and $E$ the number of edges. Assume that we are implementing the min-priority queue with a binary min-heap. Choose the anwser the that gives the tightest correct bound.

  1. $O(V^2)$
  2. $O(V^2+E)$
  3. $O(E^2)$
  4. $O((V+E)\log V)$
  5. $O(V\log V)$

Answer: 4 $O((V+E)\log V)$

As I understand it, the algorithm runs in $O((E+V) \log(V))$ with binary heap. Thus when, $E = V^2/\log(V)$, shouldn't the overall time complexity be $O(V^2)$?

$\endgroup$
2
$\begingroup$

Discrete Lizard's answer explains various aspects of the question.

Here is an explicit calculation when $E=o(V^2/\log V)$.

$$\lim_{V\to\infty}\frac{(E+V)\log V}{V^2}=\lim_{V\to\infty}\frac{E}{\dfrac{V^2}{\log V}}+\lim_{V\to\infty}\frac{V\log V}{V^2}=0+0=0$$

That means $O((E+V)\log V)\subsetneq O(V^2)$. So $O((E+V)\log V)$ is a tighter bound than $O(V^2)$ when $E=o(V^2/\log V)$.

$\endgroup$
1
$\begingroup$

First of all, note that the question does not claim $E=V^2/\log V$, but $E=o(V^2/\log V)$, which is different, see for example this table on Wikipedia.

The running time of Dijkstra with a binary heap is indeed $O((E+V)\log V)$. The question basically asks whether we can find a tighter upper bound if we know that the graph is sparse, meaning there are relatively few edges.

The answer is no. The main point is that as we know that $E=o(V^2/\log V)$, we certainly can 'fill in' the upper bound we know for $E$ and see that $O(V^2)$ is now an upper bound for the running time. However, if you do that, then you are replacing a 'known' quantity by an upper bound, which means your upper bound can only become less tight. (You can verify that the bound is chosen so that this happens here)

Another way to look at it is that 'filling in' $E$ means you are throwing away the information on the actual number of edges (which is exactly $E$) and replace it by an estimate for this number. This makes your total estimate less accurate.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.