Talk:Computational complexity

Old post

The resources (time, space, ...) used by an algorithm are subsumed as its cost.

Computational complexity is the cost of a problem as incurred by an (asymptotically) optimal algorithm.

Martin Ziegler (talk) 18:00, 5 July 2016 (UTC)

From a dab page to a true article

When editing math articles, typically when talking of the complexity of such articles, I was faced with the problem that it was a dab page that was disambiguating between two strongly related concepts. Moreover, not of the links on this dab page were convenient for an elementary description of what is computational complexity. Searching for better targets, all article that I found were either too specialized, too theoretical or too technical for what was needed.

Therefore, I have started to write this lacking article. which is presently, IMHO, a an acceptable stub. Nevertheless many things are still lacking, for which help would be welcome.

• Adding references (not really a problem, except that this takes some time; there are plenty references)
• Updating other articles on computational complexity theory
• Updating links to other articles of complexity theory for which this article would be a better target
• Adding lacking sections such as
  • Lower bounds of complexity
  • Practical aspects (increasing importance of complexity when data size increases, good complexity may differ from practical efficiency, because of constant implied by big O notation, and because the worst case may be very rare (example of simplex method, ...)
  • Complexity of parallel algorithms and randomized algorithms

These are the main things that are still lacking, but I have certainly forgotten some important aspects, that are necessary for a good introduction for the layman. D.Lazard (talk) 17:12, 3 December 2017 (UTC)

Somebody could argue that this article is a fork of Computational complexity theory or of Analysis of algorithms. This is not the case; these two articles should be linked as {{main article}} in sections of Computational complexity, but none is a convenient target for linking "complexity" in a sentence such as "the complexity of integer multiplication is $O(n^{2})$ with the elementary algorithms and $O(n\log n\log \log n)$ with the best known algorithm. D.Lazard (talk) 17:37, 3 December 2017 (UTC)