\(O(1)\) bedeutet konstante Laufzeit. Das heißt, die Laufzeit ist nicht abhängig von der Größe der Eingabe.
Beispiel. Zugriff auf ein Element eines std:array anhand der Position innerhalb des Arrays. Anhand der Adresse des Arrays und des Position des Elementes kann mittels Addition die Adresse des Elements berechnet werden. Ist die Addition \(O(1)\), dann ist auch die Ermittlung der Adresse des Elements \(O(1)\).
Gegenbeispiel. Zugriff auf ein Element einer std::list anhand der Position innerhalb der Liste. Die Liste muss elementweise vom ersten Element aus durchwandert werden bis die gewümschte Position erreicht wurde.
Amortisiert \(O(1)\) bedeutet, dass die Laufzeit für einen einzelnen Zugriff lange sein kann, aber die Gesamtlaufzeit für \(m\) Zugriffe die Laufzeit \(O(m)\) benötigt.
Beispiel. Hinzufügen eines Elements ans Ende eines std::vector. Dieser Datentyp verhält sich größtenteils wie ein Array, kann aber dynamisch vergrößert werden. Dazu wird eventuell Speicher reserviert und das zugrunde liegende Array an die neue Stelle kopiert. Das ist zwar teuer. Allerdings wird die neue Größe des Arrays berechnet indem die alte Größe mit einem Faktor m multipliziert wird. Dadurch ist es nicht bei jedem Hinzufügen eines Elements notwendig, das Array zu kopieren.
