Perso j'ai toujours trouvé que la complexité était un concept assez bidon :

- c'est défini à un facteur multiplicatif près, donc un algo en O(n) peut très bien être plus lent qu'un algo en O(n²) par exemple. Tout ce que ça garantit, c'est que l'algo en O(n) sera plus rapide que l'autre pour n supérieur à une limite, mais ça ne donne pas la valeur de cette limite (elle peut être plus élevée que le n maximum dont on a besoin).

- c'est basé sur un concept abstrait, ça ne tient pas compte du "coût" réel des opérations : une multiplication est la plupart du temps bien plus lente qu'une addition, un transfert mémoire qu'un transfert entre registres, un accès mémoire hors cache qu'un accès en cache, etc. Ce sont des choses qui influent aussi beaucoup sur les performances.

- ça suppose que le temps d'exécution soit une fonction monotone croissante qui ne dépend que de n : y'a plein de cas où c'est faux, suffit que l'algo ait des branchements conditionnels ; comment classer un algorithme très rapide dans la plupart des cas et beaucoup plus lent dans 1 ou 2 cas "pathologiques" ?