¿Qué significa

¿Qué significa $\log^{O(1)}n$ ?

Soy consciente de la notación big-O, pero esta notación no tiene sentido para mí. Tampoco puedo encontrar nada al respecto, porque no hay forma de que un motor de búsqueda interprete esto correctamente.

Para un poco de contexto, la oración donde lo encontré dice "[...] llamamos a una función [eficiente] si usa espacio $O(\log n)$ y, como máximo, $\log^{O(1)}n$ por elemento".

Debe ignorar por un momento la fuerte sensación de que la " O " está en el lugar equivocado y seguir adelante con la definición de todos modos. f ( n ) = log O ( 1 ) n significa que existen constantes k y n 0 tales que, para todos n ≥ n 0 , f ( n ) ≤ log k ⋅ 1 n = log k n .$O$$f(n) = \log^{O(1)}n$$k$$n_0$$n\geq n_0$$f(n) \leq \log^{k\cdot 1}n = \log^k n$

Tenga en cuenta que log k n significa ( log n ) k . Las funciones del formulario log O ( 1 ) n a menudo se llaman polilogarítmicas$\log^k n$$(\log n)^k$$\log^{O(1)}n$ y es posible que escuche a la gente decir: " f es polilógico  n ".$f$$n$

Notarás que es fácil demostrar que 2 n = O ( n ) , ya que 2 n ≤ k n para todo n ≥ 0 , donde k = 2 . Quizás se pregunte si 2 log n = log O ( 1 ) n . La respuesta es sí ya que, para lo suficientemente grande n , log n ≥ 2 , entonces 2 log n ≤ log 2 n para lo suficientemente grande $2n=O(n)$$2n\leq k n$$n\geq 0$$k=2$$2\log n = \log^{O(1)}n$$n$$\log n\geq 2$$2\log n \leq \log^2n$n .$n$

En una nota relacionada, a menudo verás polinomios escritos como n O ( 1 ) : la misma idea.$n^{O(1)}$

Este es un abuso de notación que puede tener sentido por la convención de marcador de posición generalmente aceptada : cada vez que encuentre un término de Landau O ( f ) , reemplácelo (en su mente o en el papel) por una función arbitraria g ∈ O $O(f)$ f ) .$g \in O(f)$

Entonces si encuentras

$\qquad f(n) = \log^{O(1)} n$

debes leer

f ( n ) = log g ( n ) n para algunos g ∈ O ( 1 ) $\qquad f(n) = \log^{g(n)} n$$g \in O(1). \hspace{5cm} (1)$

Note the difference from saying "$\log$ to the power of some constant": $g = n \mapsto 1/n$ is a distinct possibility.

Warning: The author may be employing even more abuse of notation and want you to read

$\qquad f(n) \in O(\log^{g(n)} n)$ for some $g \in O(1). \hspace{4.3cm} (2)$

Note the difference between (1) and (2); while it works out to define the same set of positive-valued functions here, this does not always work. Do not move $O$ around in expressions without care!

It means that the function grows at most as $\log$ to the power of some constant, i.e. $\log^2(n)$ or $\log^5(n)$ or $\log^{99999}(n)$...

"At most $\log^{O(1)} n$" means that there is a constant $c$ such that what is being measured is $O(\log^c n)$.

In a more general context, $f(n) \in \log^{O(1)} n$ is equivalent to the statement that there exists (possibly negative) constants $a$ and $b$ such that $f(n) \in O(\log^a n)$ and $f(n) \in \Omega(\log^b n)$.

It is easy to overlook the $\Omega(\log^b n)$ lower bound. In a setting where that would matter (which would be very uncommon if you're exclusively interested in studying asymptotic growth), you shouldn't have complete confidence that the author actually meant the lower bound, and would have to rely on the context to make sure.

The literal meaning of the notation $\log^{O(1)} n$ is doing arithmetic on the family of functions, resulting in the family of all functions $\log^{g(n)} n$, where $g(n) \in O(1)$. This works in pretty much the same as how multiplying $O(g(n))$ by $h(n)$ results in $O(g(n) h(n))$, except that you get a result that isn't expressed so simply.

Since the details of the lower bound are in probably unfamiliar territory, it's worth looking at some counterexamples. Recall that any $g(n) \in O(1)$ is bounded in magnitude; that there is a constant $c$ such that for all sufficiently large $n$, $|g(n)| < c$.

When looking at asymptotic growth, usually only the upper bound $g(n) < c$ matters, since, e.g., you already know the function is positive. However, in full generality you have to pay attention to the lower bound $g(n) > -c$.

This means, contrary to more typical uses of big-oh notation, functions that decrease too rapidly can fail to be in $\log^{O(1)} n$; for example,

A counterexample of a somewhat different sort is that $-1 \notin \log^{O(1)} n$.