1
$\begingroup$

I've been trying to find a function $T(n)$ whose asymptotic rate of growth satisfies both of the following conditions:

  1. $T(n)= o(\log^*n)$
  2. $T(n)= \omega(1)$

But I can't think of a function with this rate of growth.

$\endgroup$
1
  • $\begingroup$ Your question doesn't have anything to do with time complexity. $\endgroup$ Commented Apr 14, 2022 at 16:28

3 Answers 3

3
$\begingroup$

Take $ T(n) = (\log^*n)^{1/2}$

$\endgroup$
2
$\begingroup$

If $f(n) = o(g(n))$, then the function $h(n) = \sqrt{f(n) g(n)}$ satisfies $h(n) = o(g(n))$ and $h(n) = \omega(f(n))$.

$\endgroup$
2
$\begingroup$

A notable function that is not upper bounded by any constant but grows slower than $\log^* n$ is $\alpha(n)$, the inverse of the Ackermann function.

This function appears naturally in the analysis of Union-Find with path compression.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.