Mi malentendido fue que utilizas heurística y por ende no siempre necesariamente puede dar el resultado optimo.

Como corrección a la cantidad de ciudades que recorre en el caso de las 20 ciudades son 100 millones, 10^8 (2500000 por segundo aproximadamente).
Usando Code Blocks y con 4 núcleos de 3.0 GHz.
Usa la fuerza bruta para hacer cortocircuito, por eso visita bastante menos ciudades.

Como use programación lineal puedo comprobar que, sea cual sea el caso, obtiene el resultado optimo.
Aunque para determinar O(n) dependeria de los casos, por ende necesitaria probar con casos representativos para obtenerlo.
Sea cual sea O(n) al ser obtenido por casos representativos no seria exacto, por ende no define la relacion entre P y NP