L'algorithme

La complexité d'un algorithme récursif s'exprime en règle générale par l'intermédiaire d'une relation de récurrence. Par exemple, l'affichage des éléments d'une liste chaînée, donné par l'algorithme suivant :

Soit $u_n$ le nombre d'instructions élémentaires exécutées par $afficheListe$ si la liste $l$ comporte $n$ maillons. Si $n = 0$, l'algorithme s'exécute en temps constant. Sinon, l'appel récursif nécessite $u_{n-1}$ opérations, les autres opérations (au nombre de $k$) s'exécutent en temps constant. On définit donc $u$ comme suit : $u_n = u_{n-1} + k$, comment exprimer $u_n$ en fonction de $u_0$, de $n$ et de $k$ ?