Oletetaan, että n avainta on talletettu 1-ulotteiseen taulukkoon T[1, . . . , n]. Tehtävänä on hakeaalkiota x vastaavan avaimen arvo peräkkäishaulla (siis etsiä, milloin T[i] == x, jolloin i on avain).

Vastauksesi perustellen esitä n:n suhteen funktiona määritelty

   1. pahimman tapauksen kompleksisuus W(n),

   2. keskimääräinen kompleksisuus A(n),

   3. parhaimman tapauksen kompleksisuus B(n).

kun oletetaan, että x on taulukossa T.

Miten A(n) muuttuu, kun oletetaan, että x on taulukossa todennäköisyydellä p? Esitä A(n) kaavana, mikä pätee kaikille p:n arvoille välillä 0-1. Vertaa tuloksia arvoilla p = 1.0 ja p = 0.5.