Combining Runtime Complexity Expressions with respect to Dijkstra

Question

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|)$?)

Answer 1

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\})$.