0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Any sorting algorithm cant be faster than $O(nlogn)$. Is this what you are looking for? $\endgroup$
    – Eminem
    Dec 29, 2020 at 21:37
  • $\begingroup$ 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. $\endgroup$ Dec 29, 2020 at 21:43
  • $\begingroup$ 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... $\endgroup$
    – Mushu Nrek
    Dec 29, 2020 at 21:53
  • $\begingroup$ 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. $\endgroup$
    – J.G.
    Dec 29, 2020 at 22:20

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I think the question was whether one can construct (useful?) algorithms with such complexities in between. $\endgroup$
    – Mushu Nrek
    Dec 29, 2020 at 22:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .