0

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.

FShrike
  • 40,125
  • Any sorting algorithm cant be faster than $O(nlogn)$. Is this what you are looking for? – Eminem Dec 29 '20 at 21:37
  • Probably CS is a better place for this type of questions: https://cs.stackexchange.com/. Personally I haven't heard of anything in between $O(1)$ and $O(logN)$ if that's the question. – Stanislav Bashkyrtsev Dec 29 '20 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... – Mushu Nrek Dec 29 '20 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 '20 at 22:20

2 Answers2

1

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$).

0

Between $O(\log n)$ and $O(1)$ are things like $$ O(\log\log n) \\ O(\sqrt{\log n}) $$ and lots of others.

GEdgar
  • 111,679