Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: Anyone ever used vector<bool> ?
Date: Tue, 17 May 2022 05:37:50 -0700
Organization: A noiseless patient Spider
Lines: 17
Message-ID: <86bkvw2v35.fsf@linuxsc.com>
References: <t4rh06$1jlv$1@gioia.aioe.org> <t55hub$f9f$1@dont-email.me> <t565q5$10ln$1@gioia.aioe.org> <t5677q$fuu$1@dont-email.me> <t5albt$2g3$1@gioia.aioe.org> <jds7siF965aU1@mid.individual.net> <t5bced$16o3$1@gioia.aioe.org> <t5bdjm$v7i$2@dont-email.me> <t5bes1$fgp$1@gioia.aioe.org> <t5ds3o$667$2@dont-email.me> <t5e8l9$gar$1@gioia.aioe.org> <423b2f62-20d0-4578-a047-a4c2b03d917fn@googlegroups.com> <t5kh7g$i7n$2@dont-email.me> <t5m1a7$nfc$1@dont-email.me> <t5n8mv$q1m$1@dont-email.me> <t5sofp$3q8$1@gioia.aioe.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="0161277cd888cf27dddddc87a0dfb7f9"; logging-data="11740"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+HTrOIQuYTEzq77zSd0DSWXYDneb4Dlm0="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:j9G0u97Pr6/xkSHRQd1DPgIVoIk= sha1:W1Ln8zwdmal18gVHiuwlRMrCHYc=
Xref: csiph.com comp.lang.c++:84149

Juha Nieminen <nospam@thanks.invalid> writes:

> James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>
>> Whenever the standard specifies the complexity of an operation, an
>> implementation that has a lower complexity is always allowed.  In
>> particular, if the standard specifies O(N), an implementation that
>> sometimes takes O(1) time, and sometimes takes O(N) meets that
>> specification.  An implementation that took O(N^2) time would not.
>
> One has to be quite careful with the wording used, though.
>
> "at most O(n)", "on average O(n)" and "amortized O(n)" can mean
> quite different things.

Because James is talking about what is said in the C++ standard,
what "O(n)" means is the same as what is meant in the standard.