Koszt asymptotyczny, czyli matematyczna adnotacja , opisuje ograniczające zachowanie funkcji, ponieważ jej argument dąży do nieskończoności, tj. Jej tempa wzrostu.
Sama funkcja, np. Liczba porównań i / lub swapów, może być inna dla dwóch algorytmów o tym samym koszcie asymptotycznym, pod warunkiem, że będą rosły z tą samą szybkością.
Mówiąc dokładniej, sortowanie bąbelkowe wymaga średnio zamian na wpis (każdy wpis jest przenoszony elementarnie z pozycji początkowej do końcowej, a każda zamiana obejmuje dwa wpisy), podczas gdy sortowanie selekcji wymaga tylko (raz minimalna / maksymalna została znaleziona, jest zamieniana raz na koniec tablicy).1
Pod względem liczby porównań sortowanie bąbelkowe wymaga porównań , gdzie jest maksymalną odległością między pozycją początkową pozycji a jej pozycją końcową, która jest zwykle większa niż dla równomiernie rozłożonych wartości początkowych. Sortowanie selekcji wymaga jednak zawsze porównań .k n / 2 ( n - 1 ) × ( n - 2 ) / 2
Podsumowując, limit asymptotyczny daje dobre wyobrażenie o tym, jak rosną koszty algorytmu w stosunku do wielkości wejściowej, ale nie mówi nic o względnej wydajności różnych algorytmów w tym samym zestawie.