Exercice 2 - Listes chaînées

Déterminer la complexité dans le pire des cas (précisez de quel cas il s'agit) des opérations ci-dessous sur une liste chaînée $l = l_1 \longrightarrow l_2 \longrightarrow \ldots \longrightarrow l_n$ à $n$ éléments non triés. La seule information à notre disposition au début de l'exécution de chacun de ces algorithmes est un pointeur vers le premier élément de la liste. :

1. Affichage du $k$-ème élément de $l$.
2. Affichage des éléments de $l$.
3. Calcul de la somme cumulée des éléments de $l$.
4. Suppression du premier élément.
5. Suppression de l'élément de rang $k$, adresse du $(k-1)$-ème élément connue.
6. Suppression de l'élément de rang $k$, adresse du $(k-1)$-ème élément inconnue.
7. Recherche séquentielle d'un élément.
8. Vérification de l'appartenance de chaque élément de $l$ à une liste $q$ non triée.