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?

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

Related Questions

Integrate $int_{-infty}^{infty} frac{dx}{1+x^{12}}$using partial fractions

2  Asked on November 30, 2020

Galois connection for annhilators

1  Asked on November 30, 2020

How to compare the growth rate between $lnln n$ and $2^{lg^* n}$

0  Asked on November 30, 2020 by aesop

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

0  Asked on November 29, 2020 by user831636

Showing that sum of first $998$ cubes is divisible by $999$

2  Asked on November 29, 2020 by rebronja

Choosing two points from $[0,1]$ probability

2  Asked on November 29, 2020 by ucei

Growth of Limits of $n$-th Terms in Series

1  Asked on November 29, 2020

Why does $f^{(n)}(x)=sin(x+frac{npi}{2})$ for $f(x)=sin(x)$?

1  Asked on November 29, 2020 by cxlim

There are $6$ digits containing $1$ and $0$, only problem is that $0$’s can’t be next to each other

1  Asked on November 29, 2020 by yaz-alp-ersoy

How to show closure of ball of radius r/2 is a subset of ball with radius r

2  Asked on November 29, 2020 by hi-im-epsilon

Let $M$ be a non-empty set whose elements are sets. What are $F={A×{A} : A⊆M, A≠∅}$ and $⋃F$?

1  Asked on November 28, 2020 by andrea-burgio

Determinant of a linear transform between two different vector spaces with the same dimension

2  Asked on November 28, 2020 by lyrin

Prove $int_{mathbb{R}^d} frac{|e^{ilangle xi, y rangle} + e^{- ilangle xi, y rangle} – 2|^2 }{|y|^{d+2}}dy = c_d |xi|^2$

2  Asked on November 28, 2020 by nga-ntq

How to make an algorithm to check if you have won on a Lotto?

0  Asked on November 28, 2020 by jaakko-seppl

For every set exists another stronger set

0  Asked on November 28, 2020 by 45465

Find a formula for the general term $a_n$ of the sequence, assuming that the pattern of the first few terms continues.

1  Asked on November 27, 2020 by andrew-lewis

Examples of irreducible holomorphic function in more than one variable.

1  Asked on November 27, 2020 by alain-ngalani

Given $log_2(log_3x)=log_3(log_4y)=log_4(log_2z)$, find $x+y+z$.

3  Asked on November 27, 2020 by hongji-zhu

Which of the following statements is correct?

1  Asked on November 27, 2020 by user469754