<p>A small list with some examples:</p>
<ul>
<li>Some algorithms in computational number theory have their complexities expressed in <a href="https://en.wikipedia.org/wiki/L-notation" rel="nofollow noreferrer">L-notation</a>, and some of them feature irrational exponents: <a href="https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization#Algorithm" rel="nofollow noreferrer">Lenstra's elliptic-curve factorization</a>, <a href="https://en.wikipedia.org/wiki/Dixon%27s_factorization_method#Optimizations" rel="nofollow noreferrer">Dixon's factorization</a>, <a href="https://en.wikipedia.org/wiki/Index_calculus_algorithm#Complexity" rel="nofollow noreferrer">Index calculus algorithm</a>.</li>
<li><a href="https://en.wikipedia.org/wiki/Stooge_sort" rel="nofollow noreferrer">Stooge Sort</a> has in its complexity the exponent <code>log(3)/log(3/2)</code> which is an irrational number.</li>
<li><a href="https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication" rel="nofollow noreferrer">Toom-Cook multiplication</a>.</li>
<li>Allegedly, <a href="https://cstheory.stackexchange.com/a/32633">all SAT solvers feature</a> an irrational exponent in their complexity</li>
<li><a href="https://cstheory.stackexchange.com/a/15002">The following list</a></li>
</ul>
<p>But more generally, it should be possible to mine (and maybe even monitor) <a href="https://en.wikipedia.org/wiki/List_of_algorithms" rel="nofollow noreferrer">wikipedia's list of algorithms</a> , parse and extract the mathematical expression associated with time complexity, and possibly feed the list of expressions into a <a href="https://en.wikipedia.org/wiki/Computer_algebra_system" rel="nofollow noreferrer">CAS</a> (for example <a href="https://www.sympy.org/" rel="nofollow noreferrer">SymPy</a> using a convertor like <a href="https://github.com/augustt198/latex2sympy" rel="nofollow noreferrer">latex2sympy</a>) capable of figuring out if there are any irrational exponents involved (wikidata could be a better option if it had complete structured data coverage, example: <a href="https://www.wikidata.org/wiki/Q486598" rel="nofollow noreferrer">wikidata's quicksort page</a>). It would also be possible to extend this data collection past Wikipedia, into arXiv which apparently <a href="https://arxiv.org/help/view" rel="nofollow noreferrer">offers latex sources</a> for some of the articles, and then employ a latex parser and an expression parser to find these types of complexities.</p>
Algorithm's that has the run complexity which contains irrational exponents
<p>Hi I was wondering if there are any algorithms which has the run complexity which contain an irrational exponent. Strassen's algorithm for matrix multiplication is something I am looking for but is there more?</p>