Eyni ölçülü iki giriş üçün alqoritm tamam fərqli sürətlə işləyə bilər. Ona görə mürəkkəblik haqqında danışarkən hansı ssenarini nəzərdə tutduğumuzu demək lazımdır: ən yaxşı, ən pis və ya orta hal.

Xətti axtarış: ən yaxşı hal 1 müqayisə, orta hal təxminən n/2, ən pis hal n
Xətti axtarış: ən yaxşı hal 1 müqayisə, orta hal təxminən n/2, ən pis hal n

Xətti axtarış: üç ssenari

Siyahıda hədəfi soldan sağa axtaran funksiyanı götürək. Hədəf birinci elementdirsə, bir müqayisə kifayətdir (ən yaxşı hal). Hədəf sonuncudursa və ya yoxdursa, n müqayisə lazımdır (ən pis hal). Hədəfin hər mövqedə eyni ehtimalla ola biləcəyini fərz etsək, orta hesabla (n + 1) / 2 müqayisə olur (orta hal).

python
def linear_search(a, target):
    comparisons = 0
    for i, x in enumerate(a):
        comparisons += 1
        if x == target:
            return i, comparisons
    return -1, comparisons

a = list(range(1, 11))
print("best   ", linear_search(a, 1))
print("worst  ", linear_search(a, 10))
print("absent ", linear_search(a, 99))
total = sum(linear_search(a, t)[1] for t in a)
print("average", total / len(a))
text
best    (0, 1)
worst   (9, 10)
absent  (-1, 10)
average 5.5