Was bedeuten Worst Case, Average Case und Best Case?
Worst Case ist die maximale Laufzeit über alle Eingaben einer Größe, Best Case die minimale, Average Case die erwartete Laufzeit unter einer Eingabeverteilung.
Für Garantien ist Worst Case meist am wichtigsten.