Recherche d'une valeur et coût

def contient(liste, cible):
    for valeur in liste:           # parcours sequentiel
        if valeur == cible:
            return True            # trouve : arret immediat
    return False                   # absent apres tout le parcours

# Tests
print(contient([3, 7, 1, 9], 1))   # True
print(contient([3, 7, 1, 9], 5))   # False

Dans le meilleur des cas (valeur en première position), le coût est $O(1)$. Dans le pire des cas (valeur absente ou en dernière position), il faut parcourir toute la liste : le coût est $O(n)$.