# Time complexity with irrational exponent?

Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?

• Neat question! :) Sep 26, 2015 at 23:28
• see also golden ratio or $\pi$ in the running time. this could conceivably be a big-list...
– vzn
Sep 27, 2015 at 23:56
• Sorting a multiset is around nH+n, so if you could get H (entropy) to converge to some $n^{\alpha-1}$ that would technically qualify. I wouldn't call that "natural" though. However there might be some more natural problem where the input is reduced in this way. Sep 28, 2015 at 17:31

This can be seen more clearly in the simple case of Strassen's algorithm, which has running time $O(n^{\log_2 7})$.
And, this is not precisely what you asked, but Ryan Williams has shown that all algorithms that solve SAT in space $n^{o(1)}$ require time $n^{2 \cos(\pi/7) - o(1)}$, which is another interesting and unusual appearance of an irrational constant in TCS.
• Algorithms beyond Strassen's algorithm don't really run in $O(n^\alpha)$ for their stated exponent $\alpha$. Rather, for every $\epsilon > 0$ they run in $O_\epsilon(n^{\alpha+\epsilon})$. This is due to several limits involved in obtaining $\alpha$. Sep 27, 2015 at 12:49
• The time complexity of Strassen's algorithm is really an artifact of a Master recurrence $T(n) = a T(n/b) + f(n)$ solving to $\Theta(n^{\log_b a})$. You can come up with many of your favorite irrational numbers by instantiating $a$ and $b$ with different values. Sep 27, 2015 at 16:31
• Yes, I agree with both. I figured I was already being loose with the definition of P, and having not actually checked if the matrix multiplication exponents are irrational. Although I would be surprised if they were rational, given how they are derived. Deep down, fast matrix multiplications still echo Strassen's basic divide and conquer method, though it is described in tensor language now. Actually, though it is easy to construct algorithms as you describe with irrational $\log_b a$, I cannot think of any other natural divide and conquer algorithm with such property, besides multiplication. Sep 28, 2015 at 7:13