j'ai quelques remarques à ajouter:

1-la complexité peut être exprimée en fonction de plusieurs paramètres d'entrée

par exemple (et cela a été dit au début de cette discussion), les algo sur les graphes ont généralement une complexité exprimé en terme de |V| (le nombre de sommets) et |E| (le nombre d'arêtes)

dans le cas des graphes simples, comme on sait que |E| = O(|V|^2), il arrive que l'on simplifie l'expression obtenue
mais je trouve plus intéressant de garder la complexité exprimée en fonction des deux paramètres car ça en dit plus sur le comportement de l'algo dans le cas de graphes peu denses ou bien dans le cas de multigraphes (si l'algo a encore un sens)

2-on peut compter les opérations que l'on veut. généralement on compte l'opération la plus coûteuse mais rien n'empêche de tout compter (ça fera juste des systèmes d'équations plus compliquées à résoudre...)
on peut aussi vouloir évaluer la complexité en mémoire plutôt que celle en temps

3-l'exemple archi-classique d'algo où l'on fait une étude de la complexité en moyenne est le tri rapide (quick sort)
la complexité en comparaisons dans le pire cas est O(n^2) alors qu'elle est O(n log(n)) en moyenne