Depende do mecanismo de armazenamento.

• Para MyISAM, a contagem total de linhas é armazenada para cada tabela, então SELECT COUNT(*) FROM yourtable é uma operação O(1). Ele só precisa ler esse valor.
• Para InnoDB, a contagem total de linhas não é armazenada, portanto, é necessária uma verificação completa. Esta é uma operação O(n).

Do manual :