# Laufzeit eines Algorithmus bestimmen



## paco89 (15. Apr 2012)

hallo, ich hab da folgende aufgabe(s.Bild):

also ich muss die laufzeit dieses algorithmus' finden. ich weiß nicht wie man an diese aufgabe rangehen soll. deshalb habe ich meine lösungen einfach mal so aufgeschrieben:

also:

- best-case ist ja gleich 1. weil im besten fall ist das gesuchte element an der 1. stelle.

- als average-case, na ja dazu hatten wir eine formel: 
diese lautet: n(1- 1/2*Pr{K in E} +1/2 * Pr{K in E}), wobei Pr{K in E} für die wahrscheinlichkeit steht, dass das gesuchte element in K ist.
also wenn in der aufgabenstellung steht, dass es mit der wahrscheinlichkeit von 0.3 ein duplikat in dem array drinsteckt, dann habe ich das mal eingesetzt und erhalte 0.7*n+0.15

- aber zum worst-case, dazu fällt mir nichts ein...kann mir da jmd. vtl. weiterhelfen?


----------



## JavaGambit (15. Apr 2012)

im worst case ist es an letzter Stelle oder gar nicht drin... also steigt die Laufzeit mit jedem Element des Arrays, weil das Programm bis zum "bitteren Ende" weiter macht...


----------



## paco89 (15. Apr 2012)

d.h. also dass das worst-case gleich n , also gleich der länge des arrays is?


----------



## Paddelpirat (15. Apr 2012)

Nein, geh doch mal die Schleifen durch. Nach n Schritten weißt du im worst case noch gar nichts.

Edit: Außerdem schau dir mal die Landau-Symbole an.
Zu sagen das best case gleich 1 ist, ist falsch.


----------

