- bah quand n est borné, la notation de Landau (les O et les o) n'a aucun sens. Déjà, en théorie on devrait utiliser la notation en Θ qui est plus précise (dire qu'un algo en O(n) est un algo en O(n²) est juste mais sa complexité est surestimée), et on devrait surtout mettre en-dessous un petit « n -> ∞ ». Son seul domaine de validité, c'est quand n devient grand.
- tu n'es pas obligé d'utiliser la notation en O, justement pour les multiplications rapides, on compte précisément le nombre d'opérations + et *, ça suffit à comparer les algos en présence.
- mais rien ne t'empêche de faire de la complexité en moyenne, hein