MySQL - Complexité de :SELECT COUNT(*) FROM MyTable ;

Cela dépend du moteur de stockage.

• Pour MyISAM, le nombre total de lignes est stocké pour chaque table, donc SELECT COUNT(*) FROM yourtable est une opération O(1). Il lui suffit de lire cette valeur.
• Pour InnoDB, le nombre total de lignes n'est pas stocké, une analyse complète est donc nécessaire. Il s'agit d'une opération O(n).

À partir du manuel :