Talk:Probabilistic analysis of algorithms

Latest comment: 13 years ago by Nageh in topic Average != expected

Average != expected

edit

Average complexity does NOT mean expected complexity. While the latter is well defined (assuming a predefined randomness distribution) average-case complexity is much more subtle. For example, in cryptography an algorithm has average exponential-time complexity if the number of problems that can be solved in polynomial time is negligible. It is not too hard to construct counter-examples where the expected complexity may be polynomial or exponential. Nageh (talk) 18:16, 4 March 2011 (UTC)Reply