1
$\begingroup$

For this question, I write $\log_r n$ to be the $r$-th iterated log: $\log_1 = \log$, $\log_2 = \log\log$, $\log_3 = \log\log\log$, etc; precisely, $\log_{r+1} n = \log(\log_r n)$. Suppose I have a function $f:\mathbb N \to \mathbb R$ with the following property: $f(n) / \log_r n \to 0$ as $n \to \infty$ for all $r \in \mathbb N$. Is there any terminology for such a function? and are there any explicit examples known?

For some related ideas, consider the function $g : n \to n^{1/2}$. Then the function $f(n) = \log n$ satisfies $f(n) / g_r(n) \to 0$ as $n \to \infty$ where $g_r = g \circ g \circ \cdots \circ g$. Also, the function $h(n) = n$ is 'subexponential' in the sense that $h(n) / e^{cn} \to 0$ as $n \to \infty$ for all $c > 0$.

Should I perhaps refer to my function $f$ in the first paragraph as 'sublogarithmic'?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.