From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	ip-172-31-74-118.ec2.internal
X-Spam-Level: 
X-Spam-Status: No, score=-1.0 required=3.0 tests=BAYES_20,NICE_REPLY_A
	autolearn=ham autolearn_force=no version=3.4.6
Path: eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: "Jeffrey R.Carter" <spam.jrcarter.not@spam.acm.org.not>
Newsgroups: comp.lang.ada
Subject: Re: String Buffer
Date: Thu, 2 Dec 2021 22:06:09 +0100
Organization: A noiseless patient Spider
Message-ID: <sobcg4$tc4$1@dont-email.me>
References: <c80ebd43-1a92-4a05-a0db-7cb707191315n@googlegroups.com>
 <sob8df$vbj$1@dont-email.me> <sob9gf$5mh$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 2 Dec 2021 21:06:12 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="a3e10bdc35821c0508dd61d5653954ec";
	logging-data="30084"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18l4TQ4hXzbZNrdZ9kkVZLfDJ0p5Ej3R0I="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
 Thunderbird/91.3.1
Cancel-Lock: sha1:vyMRIqIzliihpeJnFclxzxvCvgw=
In-Reply-To: <sob9gf$5mh$1@gioia.aioe.org>
Content-Language: en-US
Xref: reader02.eternal-september.org comp.lang.ada:63192
List-Id: <comp.lang.ada>

On 2021-12-02 21:15, Dmitry A. Kazakov wrote:
> 
> It is true only to a certain degree. When comparing algorithms it is valid to 
> claim inefficiency without any context if computational complexity sufficiently 
> differs.
> 
> For example, an O(N) algorithm is unquestionably inefficient comparing to O(log 
> N) one. I leave marginal cases of very small N.

This is false. If you have the O(N) algorithm and it meets your requirements, 
then using it is more efficient than implementing the O(log N) algorithm. If you 
have both and the O(N) algorithm meets your requirements, the effort to get your 
data into a form where you can apply the O(log N) algorithm may still outweigh 
the time difference.

As for "very small N", I have worked on systems where linear search was 
efficient for sequences of 100,000 items.

The only thing you can meaningfully say about such algorithms is that one is 
O(N) and the other O(log N). Both have their uses.

Unbounded_String is needed far less than many people think, but there are 
application domains where it is much easier to achieve correctness and clarity 
with a variable-length string abstraction than without. Blanket statements about 
"efficiency" are dangerous for those working in such domains.

-- 
Jeff Carter
"After fifteen minutes I wanted to marry her, and
after a half hour I completely gave up the idea of
snatching her purse."
Take the Money and Run
136