Software cost estimation is an important area of research in software engineering. Various cost estimation model evaluation criteria (such as MMRE, MdMRE etc.) have been developed for comparing prediction accuracy among cost estimation models. All of these metrics capture the residual difference between the predicted value and the actual value in the dataset, but ignore the importance of the dataset quality. What is more, they implicitly assume the prediction model to be able to predict with up to 100% accuracy at its maximum for a given dataset. Given that these prediction models only provide an estimate based on observed historical data, absolute accuracy cannot be possibly achieved. It is therefore important to realize the theoretical maximum prediction accuracy (TMPA) for the given model with a given dataset. In this paper, we first discuss the practical importance of this notion, and propose a novel method for the determination of TMPA in the application of analogy-based software cost estimation. Specifically, we determine the TMPA of analogy using a unique dynamic K-NN approach to simulate and optimize the prediction system. The results of an empirical experiment show that our method is practical and important for researchers seeking to develop improved prediction models, because it offers an alternative for practical comparison between different prediction models.