Wikidata:Property proposal/algorithm complexity

algorithm complexity

This is a proposal of six related properties.

worst-case performance

Originally proposed at Wikidata:Property proposal/Natural science

   Done: worst-case time complexity (P3752) (Talk and documentation)

Description	time complexity of an algorithm at most
Data type	Mathematical expression
Template parameter	time at en:Template:Infobox algorithm
Domain	algorithm
Allowed values	math expression
Example	quicksort (Q486598) → O(n^2)
Source	e.g. en:Sorting algorithm
Robot and gadget jobs	No

best-case performance

Originally proposed at Wikidata:Property proposal/Natural science

   Done: best-case time complexity (P3753) (Talk and documentation)

Description	time complexity of an algorithm at least
Data type	Mathematical expression
Template parameter	time at en:Template:Infobox algorithm
Domain	algorithm
Allowed values	math expression
Example	quicksort (Q486598) → O(n log n)
Source	e.g. en:Sorting algorithm
Robot and gadget jobs	No

average performance

Originally proposed at Wikidata:Property proposal/Natural science

   Done: average time complexity (P3754) (Talk and documentation)

Description	time complexity of an algorithm on average
Data type	Mathematical expression
Template parameter	average-time at en:Template:Infobox algorithm
Domain	algorithm
Allowed values	math expression
Example	quicksort (Q486598) → O(n log n)
Source	e.g. en:Sorting algorithm
Robot and gadget jobs	No

worst-case space complexity

Originally proposed at Wikidata:Property proposal/Natural science

   Done: worst-case space complexity (P3755) (Talk and documentation)

Description	space complexity of an algorithm at most
Data type	Mathematical expression
Template parameter	space at en:Template:Infobox algorithm
Domain	algorithm
Allowed values	math expression
Example	quicksort (Q486598) → O(n)
Source	e.g. en:Sorting algorithm
Robot and gadget jobs	No

best-case space complexity

Originally proposed at Wikidata:Property proposal/Natural science

   Done: best-case space complexity (P3756) (Talk and documentation)

Description	space complexity of an algorithm at least
Data type	Mathematical expression
Template parameter	N/A
Domain	algorithm
Allowed values	math expression
Example	quicksort (Q486598) → O(log n)
Source	e.g. en:Sorting algorithm
Robot and gadget jobs	No

average space complexity

Originally proposed at Wikidata:Property proposal/Natural science

   Done: average space complexity (P3757) (Talk and documentation)

Description	space complexity of an algorithm on average
Data type	Mathematical expression
Template parameter	N/A
Domain	algorithm
Allowed values	math expression
Example	quicksort (Q486598) → O(log n)
Source	e.g. en:Sorting algorithm
Robot and gadget jobs	No

Motivation

(Add your motivation for this property here.) GZWDer (talk) 18:53, 16 January 2017 (UTC)

Discussion

•  Support best-case and worst-case property proposals. Pixeldomain (talk) 07:17, 17 January 2017 (UTC)
•  Comment How is "average" defined? Sum of the time taken to execute each permutation of the algorithm, divided by the total number of permutations? Is "average" defined by a probability distribution of a limited number of samples? I see a comment at English Wikipedia which indicates "average" is ambiguous, whereas "expected time complexity" is allegedly better defined. Pixeldomain (talk) 07:17, 17 January 2017 (UTC)
•  Support --Andrawaag (talk) 09:55, 27 January 2017 (UTC)

WikiProject Informatics has more than 50 participants and couldn't be pinged. Please post on the WikiProject's talk page instead. ChristianKl (talk) 11:16, 27 January 2017 (UTC)

•  Comment Agreed with the previous comment. Please add the relate item to the exact complexity notion associated.
•  Comment Datatype should be item, and the formula put in this item. It's less error prone as there is no ambiguity on the kind of "O" used in the formula and there is no risk of bad parsing later. Something like a "linear" item, or maybe "linear space". It's even possible to create items like "linear time algorithm". author  TomT0m / talk page 11:43, 27 January 2017 (UTC)
• (Edited: was oppose) per TomT0m unless the data type is changed. Also do we really need 6 properties for this, isn't there another way to handle it (e.g with a qualifier?) ArthurPSmith (talk) 16:35, 27 January 2017 (UTC)
•  Comment en:w:Shellsort has some examples of non-simple complexities, for example:

$O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)$. If this was an individual item, what would it be labelled? And how many items would need to be created to support the definition of all algorithm complexities? At the moment, I don't see how it would be practical to create an item for each complexity. Pixeldomain (talk) 01:30, 6 February 2017 (UTC)

• WikiProject Informatics has more than 50 participants and couldn't be pinged. Please post on the WikiProject's talk page instead. Are there additonal comments about how this property should be created? Item or formula? ChristianKl (talk) 15:52, 16 February 2017 (UTC)
•  Comment Items would clearly make querying for algorithms with similar complexity easier (identifier instead of looking for a similar string). --Tobias1984 (talk) 19:55, 16 February 2017 (UTC)
•  Comment @Tobias1984: Agreed that items have theoretical benefits over formulas, but the practical outcome will be many items without meaningful labels (see my example above). How many complexity formulas will have meaningful labels in different languages? On this basis, I still think formulas may be better suited for these properties. Pixeldomain (talk) 03:12, 17 February 2017 (UTC)
•  Support Ok, I've been thinking about this for a bit. @Pixeldomain: you have a good point on the number of different complexity items we might end up with. If we made them items I think you could label them by a rough verbal transcription of the formula, say "order N to the power 1 plus square root of 8 ln 5/2 over ln N" for your example. But I'm now somewhat convinced this is a good case where the math formula (with a regex to ensure consistency?) would work - so removed my "oppose" above and added support here to do these as math formulas after all. ArthurPSmith (talk) 17:01, 3 March 2017 (UTC)
• @ArthurPSmith, Pixeldomain, Tobias1984, TomT0m, Andrawaag, GZWDer:  Done ChristianKl (talk) 08:47, 8 March 2017 (UTC)