Sammanfattning av algoritmer (alla komplexitetsangivelser är ordogränser)

Problem/algoritm             övre gräns      undre gräns (för problem)

SÖKNING OCH SORTERING

Sortering av n element         n log n         n log n
    Mergesortering             n log n
    Heapsortering              n log n
    Insättningssortering       n^2
    Urvalssortering            n^2
    Räknesortering             n

Hitta median bland n element   n               n
    Med dekomposition          n

Sökning i sorterad n-array     log n           log n
    Binärsökning               log n

Textsökning i text av längd n  n               n
    Knuth-Morris-Pratt         n

GRAFALGORITMER   indata är en sammanhängande graf (V,E)

Grafgenomgång                  |E|             |V|+|E|
    Breddenförstsökning        |E|
    Djupetförstsökning         |E|

Minimalt spännande träd
    Prim                       |E| log |V|
    Kruskal                    |E| log |V|

Kortaste stig mellan hörn s och t, ickenegativa kantvikter
    Dijkstra                   |V|^2

Kortaste stig mellan alla par av hörn, inga cykler med negativ längd
    Med dynamisk programmering |V|^3 log |V|

Maximalt flöde 
    Bästa Ford Fulkerson       |V|^3

ARITMETIK

Diskret fouriertransform (DFT) i n punkter
    FFT                        n log n

Multiplikation av två n-tegradspolynom (enhetskostnad)
    Med FFT                    n log n

Multiplikation av två n-bitstal (bitkostnad)
    Karatsuba (Dekomposition)  n^1,58
    Schönhage-Strassen         n log n loglog n

Multiplikation av två n x n-matriser           n^2
    Strassen (dekomposition)   n^2,81
    Coppersmith-Winograd       n^2,376

GEOMETRISKA ALGORITMER

Avgör om en punkt ligger inuti en n-sidig polygon
    Med skärningsräkning       n

Konvexa höljet till n punkter  n log n         n log n
    Grahamscan                 n log n