--- Comment #7 from sjhowe at dial dot pipex dot com 2008-04-28 20:17
---
Roger
I agree with your analysis. I am slightly crestfallen as I was suspicious that
Barriato, Hofri etc's paper never mentioned worst case only approximate
case. And I have now seen BFPRT73 paper where
--- Comment #4 from sjhowe at dial dot pipex dot com 2008-04-21 18:51
---
Yes. You want a partition that is O(1) that each time round eliminates N/2
elements (bearing in mind the post-condition for nth_element where iterators
greater than the kth iterator have elements
complexity requirements
Product: gcc
Version: 4.3.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: sjhowe at dial dot pipex dot com
http
