Repository navigation
[lib] Inconsistent style in \complexity #1088
Description
Wording of complexity requirements is inconsistent in a couple of ways.
Noun-phrase or sentence?
"Exactly N applications of f."
vs.
"Applies f exactly N times.`"
vs.
"It takes approximately N comparisons."
The first form seems to be the most common.
Time or space complexity, or both?
It is not always made explicit whether the requirement is referring to time or space complexity, or both.
"Linear time." vs. "Linear."
"Constant time." vs. "Constant."
17.5.1.4 says that the Complexity: element specifies "the time and/or space complexity of the function", so being explicit about this would be good.
N log N vs. N log(N)
This is minor, but N \log(N), N \log N and N \log{N} are all used.
Activity
[lib] For showing complexity, use $N \log N$
[lib] For showing complexity, use $N \log N$
jensmaurer commentedon Mar 2, 2017
Editorial meeting consensus: Use parens for log only when the argument is long and could be ambiguous, e.g. log(N+1). "It takes" is cringe-worthy.
"Exactly N applications" and related phrases are all ok, no need to harmonize.
Time or space complexity is LWG territory.
[lib] For showing complexity, use $N \log N$
[partial.sort] Remove 'It takes' from complexity specification.
[partial.sort] Remove 'It takes' from complexity specification.
jensmaurer commentedon Mar 20, 2017
The remaining question "Time or space complexity, or both?" was sent to LWG.
jensmaurer commentedon Apr 22, 2017
LWG issue 2949