Compter les occurrences

def compte(L, x):
    n = 0
    for element in L:
        if element == x:
            n = n + 1
    return n

Un seul parcours, un compteur : la complexité est en $O(n)$, et l'on ne peut pas faire mieux — il faut bien regarder chaque élément au moins une fois pour savoir s'il vaut x.

Deux détails. On itère sur les éléments plutôt que sur les indices : c'est plus lisible et l'on ne peut pas se tromper de borne. Et sur une liste vide, la boucle ne s'exécute pas et la fonction renvoie $0$, ce qui est la bonne réponse sans qu'aucun cas particulier n'ait été écrit.