Though the time complexity you have shown may be true, the frequency analysis is entirely based on the assumption of statistical values, i.e. the frequency of the occurrence of a letter where e is the highest, t being second, et cetera. Consider this: What would happen if you attempted to break a ciphered text which has been manipulated to not conform to the statistic? Would a frequency analysis be considered reliable? Theory and practice are two sides of the same coin, they are not equivalent.
Speaking of statistics, is it not possible to have a program to detect common words to potentially find the correct deciphered text? This would easily remove the need for a person to manually look through each and every possible result.