- l'algorithme taille() est toujours O(n) : ATTENTION !!! Lisez moi bien : je n'ai pas dit qu'il n'était pas O(1) !! Rappel : O(1) est INCLUS dans O(n) : O(n) veut dire « au pire comme "c fois n" » ;
donc, dans tous les cas où ce O(n) suffit pour conclure et ne change pas la conclusion (p.ex. parce que la complexité finale globale de l'algorithme étudié est plus grande que O(n)), il n'y a rien à dire : on s'attend à ce que vous sachiez que taille est en O(n) ; - pour les cas où le fait qu'il soit « en O(n) mais pas en O(1) » ou qu'il soit en O(1) fait une différence, alors vous pouvez supposer qu'il est en O(1), mais il faudra le dire explicitement pour montrer que vous avez vu le problème
(ou alors, évidemment, si c'est clairement demandé, faire la distinction et le calcul dans les deux cas, comme nous l'avons fait en cours ; mais ce sera plus rare et, comme dit, explicitement demandé).
C'est une très bonne question et la réponse de M. Protais reste valable aussi dans le cas général :