Eine lineare Suche vergleicht die Elemente eines Arrays mit 100 verschiedenen Werten der Reihe nach von vorn, um einen Zielwert zu finden. Der Zielwert ist immer im Array enthalten und steht mit gleicher Wahrscheinlichkeit an jeder Position. Wie viele Vergleiche sind im Mittel nötig?

Antwort: B. 50,5

Steht der Zielwert an Position k, sind k Vergleiche nötig; im Mittel also (1 + 2 + … + 100) / 100 = 50,5, allgemein (n + 1)/2. Im besten Fall (Zielwert ganz vorn) genügt 1 Vergleich, im schlechtesten Fall (Zielwert am Ende) sind es 100. Sowohl der mittlere als auch der schlechteste Fall sind proportional zu n, die Komplexität ist also O(n). Etwa 7 entspricht log₂ 100 ≈ 6,6, der Schrittzahl einer binären Suche, die sich nur auf sortierte Daten anwenden lässt.