public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
From: "andersk at mit dot edu" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/35968] nth_element fails to meet its complexity requirements
Date: Mon, 06 Apr 2020 18:32:35 +0000	[thread overview]
Message-ID: <bug-35968-4-ZZBN6lFRTS@http.gcc.gnu.org/bugzilla/> (raw)
In-Reply-To: <bug-35968-4@http.gcc.gnu.org/bugzilla/>

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968

--- Comment #13 from Anders Kaseorg <andersk at mit dot edu> ---
(In reply to Patrick J. LoPresti from comment #12)
> I am familiar with the usual algorithmic complexity definitions.
> 
> So, just to be clear... Your assertion is that the C++ standards committee
> adopted a specification that rules out a deterministic implementation?

I should have been clearer: I’m saying it rules out quickselect with a
deterministic pivot selection rule that doesn’t inspect Θ(n) elements. 
Quickselect with randomized Θ(1) pivot selection would satisfy the
specification, as would quickselect with deterministic Θ(n) pivot selection by
median-of-medians or similar, but not quickselect with deterministic Θ(1) pivot
selection by taking the first element or similar.

  parent reply	other threads:[~2020-04-06 18:32 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <bug-35968-4@http.gcc.gnu.org/bugzilla/>
2015-05-14  0:22 ` lopresti at gmail dot com
2020-04-05 21:56 ` andersk at mit dot edu
2020-04-06 15:53 ` lopresti at gmail dot com
2020-04-06 18:32 ` andersk at mit dot edu [this message]
2020-06-19 15:35 ` sjhowe at dial dot pipex.com
2008-04-17 20:39 [Bug libstdc++/35968] New: " sjhowe at dial dot pipex dot com
2008-04-20 17:31 ` [Bug libstdc++/35968] " pcarlini at suse dot de
2008-04-21  3:23 ` roger at eyesopen dot com
2008-04-21  8:25 ` pcarlini at suse dot de
2008-04-21 18:52 ` sjhowe at dial dot pipex dot com
2008-04-24 15:02 ` roger at eyesopen dot com
2008-04-24 23:40 ` bkoz at gcc dot gnu dot org
2008-04-28 20:18 ` sjhowe at dial dot pipex dot com
2009-12-15 17:19 ` paolo dot carlini at oracle dot com
2010-01-28 17:17 ` paolo dot carlini at oracle dot com

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=bug-35968-4-ZZBN6lFRTS@http.gcc.gnu.org/bugzilla/ \
    --to=gcc-bugzilla@gcc.gnu.org \
    --cc=gcc-bugs@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).