|
|
|
|
|
|
by DSrcl
3230 days ago
|
|
|
Labelling an operation -- number of steps of which upper-bounded by 6 -- "effectively constant" is different from considering any real world algorithm with bounded input size. Calling Scala's immutable vector ops "effectively constant" is not a stretch/hack by any means, considering we also say the same for integer addition and multiplication. |
|
|
This rationale ad absurdum means we can call an in-memory linear search "effectively constant" because we have an upper-bound of 2^32 or 2^64, depending on processor architecture.
Yes, log32 is very nice. Even log2 is pretty nice though, and we don't call that "effectively constant", because we already have a much more precise and well defined term for it - "logarithmic" - which the docs also use: http://docs.scala-lang.org/overviews/collections/performance...
You might be able to tell me with a straight face that labeling log32 "effectively constant" and log2 "logarithmic" is "correct enough". But can you tell me with that same straight face, that labeling it "Log32" (or even just "Log") isn't just as correct, more informative, and less confusing?