1
$\begingroup$

According to the Wikipedia page on the Push-relabel maximum flow algorithm:

Subcubic $O(|V||E| \log\frac{|V|^2}{|E|})$ time complexity can be achieved using dynamic trees, although in practice it is less efficient.

What if $|E| = |V|^2$? Don't we then have this?

$$O(|V||E| \log\frac{|V|^2}{|V|^2})$$ $$O(|V||E| \log 1)$$ $$O(|V||E| 0)$$ $$O(0)$$

There's no way this can be right, so what am I misunderstanding?

$\endgroup$
2
$\begingroup$

First of all, we usually assume that there are no self-loops. As a consequence, $|E| \leq |V|(|V| - 1) < |V|^2$.


That aside, there is (probably) a misuse of Landau notation here.

The given bound is (probably) not correct for all (families of) graphs. For instance, if $|E| = 0$ the same arithmetic issue occurs but the algorithm will certainly have non-zero running time.

The authors probably simplified away terms of the order of, say, $\Theta(|V|)$ or $\Theta(|E|)$. They do this because they are asymptotically dominated by the given term -- if all quantities are non-zero. This is a fundamental problem with using Landau notation with more than one variable without being rigorous about it.

So, even if the leading term would become zero (which can certainly happen and be correct!) lower-order terms would be non-zero and lead to useful bounds.

Example

Consider this very simple algorithm:

1 def algo(n, m) 
2   x = 0
3   for i = 1 .. n 
4     for j = 1 .. m
5       x += 1
6   return x

A standard analysis tells you immediately that the running-time is in $\Theta(nm)$ as that is how often the line x += 1 will be executed. Now, if n or m is zero, does the algorithm have zero running time? No!

A more precise analysis leads to the running-time being

$\qquad c_1 + c_2 n + c_3 m + c_4 nm$

with suitable constants $c_1$ (cost of lines 2 and 6, setup of line 3), $c_2$ (management of line 3, setup of line 4), $c_3$ (management of line 4) and $c_4$ (line 5).

Background

Landau notation only makes sense if the parameters go to infinity in suitable ways. We can not just insert finite values for some parameters and expect it to behave well.

Refer to A general definition of the O-notation for algorithm analysis by Kalle Rutanen et al. for details.

$\endgroup$

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.