Coevolutionary Genetic Algorithms (CGAs) have been used as a useful optimization technique in a number of applications, and their results show that CGAs outperform traditional genetic algorithms under certain conditions. However, there was no systematic research that found those conditions and the reason why CGAs outperform the traditional genetic algorithm. Therefore this paper formulates the class of CGAs which shows better performance, and proves the reason. The definition of formulated CGA and problem cover the CGAs and the problems which showed good performance in the literature. Two theorems are provided to show the performance of the defined CGA, with respect to both the quality of the solution and the amount of computational time. The theorems are justified by an analysis carried on the experiments presented in literature. A supplementary experimental result on a reasonably difficult problem for the traditional genetic algorithms supports the theorems.