Pergunta

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?)

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top