Talk:Computational complexity: Difference between revisions

Revision as of 17:12, 3 December 2017

Latest revision as of 23:58, 8 March 2024

(8 intermediate revisions by 6 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{WikiProjectBannerShell|1=

{{WikiProject Computing|class=stub|importance=Top}}

{{WikiProject Computer science|class=stub|importance=top}}

{{mathsWikiProject rating|class=stubMathematics|importance=high|field=discrete}}

}}

{{annual readership|scale=log}}

==Old post==

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

Line 17 ⟶ 19:

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

Line 24 ⟶ 26:

** 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. [[User:D.Lazard|D.Lazard]] ([[User talk: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 {{tl|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 <math>O(n^2)</math> with the elementary algorithms and <math>O(n\log n \log \log n)</math> with the best known algorithm. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:37, 3 December 2017 (UTC)