0
$\begingroup$

If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity statement:

$$ O(\text{my algorithm}) = O(|V|\mathop{log}|V| + |E|\mathop{log}|V|) + O(|V|^2) $$

Assuming Dijkstra's is implemented with the binary heap.


My problem is that I realized that, worst case, $|E| = |V|^2$, and the statement rewrites as:

$$ O(|V|^2 \mathop{log}|V|) + O(|V|^2) = O(|V|^2\mathop{log}|V|) $$

But, the rest of the time, the algorithm is $O(|V|^2)$, especially if $|E| < |V|$.


What is the correct runtime in this situation? And what is the reasoning behind the correct runtime statement? Because it seems like, to me, just listing out Dijkstra's runtime would be incorrect, since it is only true when the graph is dense... (can I add them together, like: $O(|V|^2 + |E|\mathop{log}|V|)$?)

$\endgroup$
2
$\begingroup$

Yes, you can just add them together. If $|E|=O(|V|^2/\log|V|)$, then $O(|V|^2+|E|\log|V|)$ is the same thing as $O(|V|^2|)$, since the first term dominates. If $|E|=\Omega(|V|^2/\log|V|)$, then it's the same thing as $O(|E|\log|V|)$, since the second term dominates.

It might help your thinking to bear in mind that $f + g = O(\max\{f,g\})$.

$\endgroup$
  • $\begingroup$ I wanted to write your last expression exactly...but I wasn't sure if I could, or that I could just add them. Thank you! $\endgroup$ – donlan Feb 22 '17 at 0:14

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.