This is an old revision of this page, as edited by Nageh(talk | contribs) at 18:16, 4 March 2011(average != expected). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.Revision as of 18:16, 4 March 2011 by Nageh(talk | contribs)(average != expected)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.
Average != expected
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]
