According to 25.3.2, the complexity of nth_element() is "linear on
average".  Can somebody elaborate a little on that?  Don't we need some
kind of definition of "average" to hang our computational hat on?

Thanks,

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.13c47cae8daa8aae989708@news.supernews.com...
> According to 25.3.2, the complexity of nth_element() is "linear on
> average".  Can somebody elaborate a little on that?  Don't we need some
> kind of definition of "average" to hang our computational hat on?

Sometimes called 'expected.'  Sometimes average, for this kind of operation,
is defined as the total time for all possible permutations, divided by the
number of permutations.  Sometimes some permutations are more heavily
weighted.

Note that 'average' is also used for sort(), where I believe the "founding
fathers" were thinking quicksort with a decent method of finding the pivot
element.

For nth_element I believe the founding fathers were thinking of quicksort,
but for each level of recursion only partition the "half" containing the nth
element.  If you are lucky this takes about 2*N comparisons, and you don't
expect it to take many more than that, but for pathological cases it can
take about N*N/2 comparisons.

It is possible to implement nth_element in O(N) worst-case time, but it is
typically slower than the other approach.  It should be possible to use
methods analogous to introsort to implement nth_element in worst case O(N),
but typically as fast as the "quicksort" solution:

1) Use quicksort-style partitioning until at most 6*N comparisons have
occurred (the 6 is an arbitrary constant).  Note that the number of
comparisons is easily counted outside of the inner loops.
2) Use a slower O(N) worst-case method on the remaining partition if
necessary.  The method I reference below is linear, but the proportionality
constant is quite large.

For a reference on finding the nth element in O(N) worst case time, see
algorithm 3.6, SELECT, in Aho, Hopcroft and Ullman, "The Design and Analysis
of Computer Algorithms."  They reference Blum,Floyd,Pratt,Rivest and Tarjan
[1972], "Time bounds for selection," "J. Computer and System Sciences 7:4"



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Scott Meyers <smeyers@aristeia.com> wrote:

> According to 25.3.2, the complexity of nth_element() is "linear on
> average".  Can somebody elaborate a little on that?  Don't we need some
> kind of definition of "average" to hang our computational hat on?
>

Expected value is O(n).

--
Harry Erwin, PhD, <mailto:herwin@gmu.edu>,Computational Neuroscientist
(modeling bat behavior), Senior SW Analyst and Security Engineer, and
Adjunct Professor of Computer Science, GMU. Looking--CV available at:
<http://mason.gmu.edu/~herwin/CV.htm>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]