4
$\begingroup$

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well represented by $\Theta(n)$. This makes me ask whether it is possible to define a set of "representative functions" which are totally ordered by the $o$-notation?

Concretely, let $F$ be the space of all positive, monotonically increasing real functions on $N$ (the natural numbers). I am looking for a subset $G\subseteq F$ with the following properties:

  1. For every two functions $g_1,g_2 \in G$, either $g_1(n) = o(g_2(n))$ or $g_2(n) = o(g_1(n))$.

  2. For every function $f\in F$, there is a function $g\in G$ with $g(n)=\Theta(f(n))$

Does there exist such a set? If so, how can it be represented (e.g. how many real parameters are required?)

$\endgroup$
  • 1
    $\begingroup$ Maybe this question would be better on math.stackexchange. $\endgroup$ – Tom Cornebize Apr 24 '15 at 13:02
  • 1
    $\begingroup$ @TomCornebize I thought of asking this in math.SE, but found it difficult to understand the motivation. The motivation is from computer science. $\endgroup$ – Erel Segal-Halevi Apr 24 '15 at 13:05
  • 1
    $\begingroup$ The answer to the existence question should be "yes", assuming the axiom of choice, but this does not necessarily imply representability. Note that even for functions $\mathbb{N}\to\mathbb{N}$ you would have consider monstrosities such as the fast-growing hierarchies (en.wikipedia.org/wiki/Fast-growing_hierarchy). $\endgroup$ – Klaus Draeger Apr 24 '15 at 14:04
  • $\begingroup$ It may be easier to formulate a normal form; drop all non-dominant summands and constant factors, for instance. But then, the set of all functions is uncountable while that of those we can write down (with any fixed syntax and semantics) is countable, so this "visual" approach won't cover most functions. $\endgroup$ – Raphael Apr 24 '15 at 14:06
  • 3
    $\begingroup$ Ah, but I found this: mathoverflow.net/questions/45510/… $\endgroup$ – Erel Segal-Halevi Apr 24 '15 at 14:16
1
$\begingroup$

This question is very natural since most if not all common functions that appear in the runtime-analysis of algorithms form a totally ordered set in terms of little $o$-notation or big $\Omega$-notation such as shown in this answer by Robert S. Barnes or this answer by Kelalaka.


However, there is no such totally-ordered set of representative functions for all positive increasing functions.

The basic reason is the first property, when applied to $F$, does not define a total-order.

Define two strictly increasing $f_1(n)$ and $f_2(n)$ from $\Bbb N$ to $\Bbb N$.

$$f_1(n)=2^{(2\lceil\frac {n+1}2\rceil)^2+n}$$ $$f_2(n)=2^{(2\lfloor\frac {n}2\rfloor+1)^2+n}$$

Then $$\sup\lim _{n\to\infty}\frac {f_1(n)}{f_2(n)} \ge \lim_{n=2i+1\to\infty}\frac {f_1(n)}{f_2(n)} =\lim_{i\to\infty}\frac {2^{(2(i+1))^2+2i+1}}{2^{(2i+1)^2+2i+1}} =\lim_{i\to\infty}2^{4i+3}=\infty$$

$$\sup\lim _{n\to\infty}\frac {f_2(n)}{f_1(n)} \ge \lim_{n=2i\to\infty}\frac {f_2(n)}{f_1(n)} =\lim_{i\to\infty}\frac {2^{(2i+1)^2+2i}}{2^{(2i)^2+2i}} =\lim_{i\to\infty}2^{4i+1} =\infty$$

In plain words, neither of $f_1(n)$ and $f_2(n)$ grows asymptotically the same or faster than the other one ignoring a constant factor.

Let $F$ and $G$ be defined as in the question. Suppose $G$ exists. Then there is $g_1, g_2\in G$ such that $g_1(n)=\Theta(f_1(n))$ and $g_2(n)=\Theta(f_2(n))$. Then $g_1(n)>c_1(f_1(n))$ for some constant $c_1>0$ and $g_2(n)<d_2(f_2(n))$ for some constant $d_2$. (In usual cases, we have to say "for $n$ large enough". However, that clause can be omitted since all values here are positive. Anyway, we can add that clause as well.)

$$\sup\lim _{n\to\infty}\frac {g_1(n)}{g_2(n)} \ge \sup\lim_{n\to\infty}\frac {c_1f_1(n)}{d_2f_2(n)} \ge \frac{c_1}{d_2}\sup\lim_{n\to\infty}\frac {f_1(n)}{f_2(n)} =\infty $$

Symmetrically, $\sup\lim_{n\to\infty}\dfrac {g_2(n)}{g_1(n)}=\infty$. We see that $g_1\not=g_2$ but neither $g_1(n) = o(g_2(n))$ nor $g_2(n) = o(g_1(n))$. This contradition shows $G$ does not exist.


How about if we drop the first requirement so that the functions in $G$ are not required to dominate each other?

Then this question becomes closely related to the question Big O notation and the maximal set of comparable functions as found by OP, where a couple of enlightening answers explain the situation pretty well, indicating there is hardly any hope for a nice positive answer. Even countably-infinitely real parameters cannot parametrize continuously a set of representative functions in the equivalence classes of increasing functions where two functions are in the same equivalence class if they are related by $\Theta$ and each function only uses finitely-many parameters.


Explicit rigorous answers to the following exercises might be long. However, the ideas should be simple for experienced users.

(Exercise 1.) For any given positive integer $n$, construct $n$ increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(f_2)$ nor $f_2=O(f_1)$.

(Exercise 2.) Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(f_2)$ nor $f_2=O(f_1)$.

(Exercise 3.) Let $h(n)$ be a given function from $\Bbb N$ to $\Bbb N$. Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(h\ f_2)$ nor $f_2=O(h\ f_1)$.

$\endgroup$
  • $\begingroup$ Cool example! I didn't think that there could be functions that are incomparable by the $O$ notation. We could define a relaxed notation that allows functions to differ not only by a constant factor but also by an exponential function of $n$. But then we could find another pair of functions that is incomparable by the new notation too. $\endgroup$ – Erel Segal-Halevi Jan 17 at 10:30

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.