Why write computational complexity as $O\left( m n \log (n^2 / m) \right)$? On slide 40 of this presentation, an algorithm is described as having a complexity of $O\left( m n \log (n^2 / m) \right)$. But since $$\log (n^2 / m) = 2 \log n - \log m$$
is itself $O(\log n)$, wouldn't it be equivalent to write the original complexity as $O\left( m n \log n \right)$?
Is this notation meant to emphasize that this algorithm is marginally worse than the $O\left( m n \log n \right)$ algorithm listed above it?
 A: The factor $\log(n^2/m)$ can be better than $O(\log n)$, because the number of edges $m$ can vary to some extent independently of the number of nodes $n$.
On the low end, we have $m \ge n-1$ for any reasonable network. If a node other than $t$ doesn't have any edges out of it, we can delete it without changing the problem, so we may assume every node other than $t$ has at least one edge leaving it - and then $m \ge n-1$.
On the high end, we have $m \le (n-1)^2 < n^2$ because each node other than $t$ can have at most $n-1$ edges out of it (and $t$ shouldn't have any, because they're pointless).
So for sparse networks where $m = O(n)$, $\log (n^2/m)$ is indeed as large as $\Omega(\log n)$, and the two algorithms with complexity $O(mn \log (n^2/m))$ and $O(mn \log n)$ are equivalent.
On the other hand, for dense networks where $m = \Omega(n^2)$, $\log(n^2/m)$ is just $O(1)$, and the algorithm with complexity $O(mn \log(n^2/m))$ is better: it's just $O(mn)$.
This is also the reason why we write the factor $\log (n^2/m)$ the way we do: the ratio $\frac{m}{n^2}$ measures the density of the network, so it's an independently interesting parameter.
