What does $\text{poly}$ stand for in $O(\log^{10.5}n \cdot \text{poly}(\log \log n))$?

Question

I posted this question on cstheory and found that "poly(f(n))" is shorthand for "polynomial in f(n)" or $f(n)^{O(1)}$, hence poly(log log n) is shorthand for $(log log n)^{O(1)}$. However, I don't understand the notation where the big oh is an exponent. I understand big oh notation but not when big oh itself is an exponent. Why have the word poly at all in the expression? Can anybody explain how this works or refer me to some articles?

Answer 1

Putting the $O(1)$ in the exponent doesn't involve any special notation or hidden meaning that you haven't already seen.

As you probably already know, if something is in $O(1)$, it's bounded above by some constant $c$. By saying $f(n)^{O(1)}$, all they are saying now is that the exponent is bounded above by some constant $c$.

$poly(f(n))$ means that the complexity of whatever you are analyzing is upper bounded by some polynomial in $f(n)$. With regards to the $f(n)^{O(1)}$ bit, the constant would coincide with the degree of that polynomial.

Answer 2

In general, embedding $O(f(n))$ into a larger expression $H(n,O(f(n)))$ means by definition the class of functions bounded by some $H(n,g(n))$ where $g(n)\in O(f(n))$. In the particular case where $H(n,e)=h(n)^e$ and $f(n)=1$ one gets that $H(n,O(f(n)))=h(n)^{O(1)}$ is the class of functions $h(n)^{g(n)}$ where $g(n)$ is any bounded function of $n$. The class contains any monomial $h(n)^c$ in $h(n)$ (with constant exponent $c$), and if $g(n)$ is bounded by $c$ then $h(n)^{g(n)}$ is bounded by $h(n)^c$ (at least under the reasonable assumption that $h(n)\geq1$), so we are looking at the class of functions of $n$ bounded by some $h(n)^c$, or equivalently by some polynomial in$~h(n)$.