Christopher Wright wrote:
Andrei Alexandrescu wrote:
Steve Schveighoffer wrote:
BTW, what happens if you pass a sorted list into find? Intuitively,
you'd assume you can pass as assumeSorted? But you can't really do
anything but linear search?
It's up to the designer of the API. Passing a sorted forward range
into sort will cut the average search time in half, which does not
improve complexity.
How does this work? find in a sorted linked list has the same expected
runtime as in an unsorted one -- on average, 0.5 * length. Assuming that
comparisons and iterating are equally expensive, that is. If you assume
that comparison is more expensive, you can do better, though cheaper
comparisons don't benefit you at all.
We're saying the same thing.
Andrei
