As a complement to the periodogram, low-complexity frequency estimators are of interest. One such estimator is based on Prony's method and rely on phase information of the auto-correlations. Both performance and computational complexity are functions of the choice of correlations used in the estimator and often we have a trade off situation. In this paper, frequency estimation from an arbitrary set of estimated auto-correlations is studied. We further introduce a design strategy by optimizing a performance criterion given a predetermined computational constraint. We illustrate this by numerical examples.