# What is the best theoretical Big O for some ideal algorithm?

Big O notation has many commonly found real-world examples, like O(N), O(log N), O(N log N),... and so on. Other than a constant Big-O like O(1), is there some theoretical golden "value" of O that some perfectly efficient algorithm could achieve, one that is faster than O(log N)? As in, an function with O([this expression]) could never be reduced to a less time-complex form?

Apologies if this is the wrong StackExchange for this, but this seems more a math question to me. Thanks for any help.

• Any sorting algorithm cant be faster than $O(nlogn)$. Is this what you are looking for? Dec 29, 2020 at 21:37
• Probably CS is a better place for this type of questions: cs.stackexchange.com. Personally I haven't heard of anything in between $O(1)$ and $O(logN)$ if that's the question. Dec 29, 2020 at 21:43
• I am not sure what your question is, but it is very simple to construct an algorithm which has any complexity you like... If you want the complexity $f(n)$, then the algorithm "enumerate all numbers between 1 and $f(n)$" has exactly complexity $f(n)$... There are surely less stupid things one might do... Dec 29, 2020 at 21:53
• One challenge in finding a $o(\log N)$ algorithm is that it seems merely telling the function which value of $N$ it has to run on takes $O(\log N)$ time just passing in $N$'s digits. However, that's probably considered "free". For example, def f(N): return 1 would usually be described as running in $O(1)$ time.
– J.G.
Dec 29, 2020 at 22:20

A famous example is given by the Union-Find problem, where the amortized time can be made $$\Theta(\alpha(n))$$ where $$\alpha(n)$$ is the Inverse Ackermann function, which is extremely slowly growing (slower than the iterated logarithm $$\log^*(n)$$). For all practical $$n$$, the function value does not exceed $$5$$ (it would take much much much more than the number of subsets of atoms in the universe to reach $$5$$).
Between $$O(\log n)$$ and $$O(1)$$ are things like $$O(\log\log n) \\ O(\sqrt{\log n})$$ and lots of others.