Why write computational complexity as $Oleft( m n log (n^2 / m) right)$?

Mathematics Asked on November 7, 2020

On slide 40 of this presentation, an algorithm is described as having a complexity of $Oleft( 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 $Oleft( m n log n right)$?

Is this notation meant to emphasize that this algorithm is marginally worse than the $Oleft( m n log n right)$ algorithm listed above it?

One Answer

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.

Correct answer by Misha Lavrov on November 7, 2020

Add your own answers!

Related Questions

How do I use only NAND operators to express OR, NOT, and AND?

0  Asked on November 29, 2020 by user831636


For how many values of n, will P(n) be false?

2  Asked on November 29, 2020 by asad-ahmad


For every set exists another stronger set

0  Asked on November 28, 2020 by 45465


Which of the following statements is correct?

1  Asked on November 27, 2020 by user469754


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP