Laufzeit eines Algorithmus bestimmen

[paco89]

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]

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]

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

 

[Paddelpirat]

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.