Asymptotically optimal algorithm

<h2 id="formal-definitions">Formal definitions</h2>
<p>Formally, suppose that we have a lower-bound theorem showing that a problem requires Ω(f(<i>n</i>)) time to solve for an instance (input) of size <i>n</i> (see <a href="/facts/Big_O_notation/weFFjSWg">Big O notation § Big Omega notation</a> for the definition of Ω). Then, an algorithm which solves the problem in O(f(<i>n</i>)) time is said to be asymptotically optimal. This can also be expressed using limits: suppose that b(<i>n</i>) is a lower bound on the running time, and a given algorithm takes time t(<i>n</i>). Then the algorithm is asymptotically optimal if:
</p>

lim
          
            n
            →
            ∞
          
        
        
          
            
              t
              (
              n
              )
            
            
              b
              (
              n
              )
            
          
        
        <
        ∞
        .
      
    
    {\displaystyle \lim _{n\rightarrow \infty }{\frac {t(n)}{b(n)}}<\infty .}

<p>This limit, if it exists, is always at least 1, as t(<i>n</i>) ≥ b(<i>n</i>).
</p><p>Although usually applied to time efficiency, an algorithm can be said to use asymptotically optimal space, random bits, number of processors, or any other resource commonly measured using big-O notation.
</p><p>Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular <a href="/facts/Abstract_machine/zuC4RKLn">abstract machine</a> model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.
</p>
<h2 id="speedup">Speedup</h2>
<p>The nonexistence of an asymptotically optimal algorithm is called speedup. <a href="/facts/Blum%27s_speedup_theorem/jQMKIla6">Blum's speedup theorem</a> shows that there exist artificially constructed problems with speedup. However, it is an <a href="/facts/Open_problem/VuR6yLsW">open problem</a> whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an 
  
    
      
        O
        (
        n
        α
        (
        n
        )
        )
      
    
    {\displaystyle O(n\alpha (n))}
  
 algorithm for finding <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning trees</a>, where 
  
    
      
        α
        (
        n
        )
      
    
    {\displaystyle \alpha (n)}
  
 is the very slowly growing inverse of the <a href="/facts/Ackermann_function/WQNpCWHn">Ackermann function</a>, but the best known lower bound is the trivial 
  
    
      
        Ω
        (
        n
        )
      
    
    {\displaystyle \Omega (n)}
  
. Whether this algorithm is asymptotically optimal is unknown, and would be likely to be hailed as a significant result if it were resolved either way. Coppersmith and Winograd (1982) proved that matrix multiplication has a weak form of speed-up among a restricted class of algorithms (Strassen-type bilinear identities with lambda-computation).
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Element_uniqueness_problem/Mwxm6SRv">Element uniqueness problem</a></li>
<li><a href="/facts/Asymptotic_computational_complexity/fMuA7mEP">Asymptotic computational complexity</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo <a href="/wiki/Robert_Sedgewick_(computer_scientist)" target="_blank">/wiki/Robert_Sedgewick_(computer_scientist)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Asymptotically optimal algorithm open-in-new

Asymptotically optimal algorithm