Re: Is it possible to delete an element from a sorted array with O(1) time?

* Logan Shaw:
Alf P. Steinbach wrote:
* Kai-Uwe Bux:
The OPs question was

Is it possible to delete an element from a sorted array with O(1) time?

It uses "an" and "a". Because of ambiguity in indeterminate articles in the
English language, there are at least four basic ways of reading the
question:

(a) Is it possible to delete some element from some sorted array with O(1)
time?

(b) Is it possible to delete some element from any sorted array with O(1)
time?

(c) Is there some sorted array from which any element can be deleted with
O(1) time?

(d) Is it possible to delete any element from any sorted array with O(1)
time.

Your answer ("yes") relied on a disambiguation of the OPs question.

Sorry, that is incorrect.

The question as stated is unambigious and corresponds to (a), which I demonstrated simply by doing /exactly/ what was asked for, literally.

The question is only unambiguous if the only requirement to make a valid
attempt to communicate is taking the most literal possible meaning and
ignoring all other meanings that are reasonable given the context.

However, if you study the philosophy of language, you will quickly
realize that, in a language without formal definitions of the vocabulary
(or even rules of grammar), completely unambiguous communication is
not possible. Furthermore, for practical reasons, communication in
natural languages like English typically leaves out a lot of information.
It is the listener's role to fill in the missing information by drawing
on shared assumptions and practical considerations to imagine all the
possible interpretations and taking the one that is most reasonable.

In other words, only if you to start off with the twin false assumptions
that English is a formal language capable of mathematical rigor and that
the original poster intends to use English in this manner, only then is
(a) the only valid interpretation.

Or to put it yet another way, natural language communication is a
mixture of semantics and pragmatics. If you deny the former, you
are not making a complete attempt to communicate.

It is true that it's possible to write vague and misleading statements and questions in English, yes, e.g. like the above.

But from that demonstrated possibility it does not follow that any particular question must be vague.

And in fact, the original question was clear, and further, we have debated the possible other reasonable interpretations of the question.


However, we have discussed how also (b), (c) and (d) must necessarily yield the answer "yes".

Only with

1) a particular interpretation of /delete/, plus

There are two classes of interpretation for 'delete': the ones
that include and the ones that exclude the degenerate cases of
lazy evaluation.

Since the degenerate cases of lazy evaluation make the original
question trivial and meaningless but the question is meaningful
if you exclude the degenerate cases, a person who is making a
genuine attempt to understand the question would have to assume
the interpretation of 'delete' must exclude degenerate cases of
lazy evaluation.

This is irrelevant to the earlier discussion, which has not included lazy evaluation. However, it's also wrong. So just for completeness: lazy evaluation is one extra possibility, not so far discussed, for doing what the OP asked, and it has some practical significance.


2) adding in a universal quantification (that it should always be
possible),

Once again, the question is wholly trivial and uninteresting if you
don't include both universal quantifiers.

This debate has shown that to be incorrect with respect to those who have joined the thread, except you. And I know especially Kai-Uwe as a fairly intelligent & knowledgable guy, and judging from the start of the thread (ignoring what may have followed from locked-in positions) this was not at all "trivial and uninteresting": in fact it took a bit of discussion to just clarify the possibility. It seems, then, that there are only two possibilities: either you don't really understand what you're talking about, or else you happen to be a genius, in which case it may be "wholly trivial" to you, but not to others.


Therefore the only truly
valid interpretation is the one where the universal quantifiers
are included.

It may be a not unreasonable interpretation, for one concerned with interpretations and the nuances of the English language, to assume that a question that appears meaningless must instead have been meant as an apparently more meaningful question that involves most of the words that were mentioned, plus some that the OP plainly just forgot to include.

Instead of "can a car drive faster than 100 mph", which historically some scientists thought they'd proven was impossible, you're saying that what they really answered no to was "can every car continously drive under only its own power, faster than 100 mph, for any length of time...", thus, hurray, proving the old nay-sayers right.

But I'm sorry: that universally quantified question is utterly trivial and meaningless, and since you maintain that someone could reasonably mean to ask that question, I doubt that you're a genius.

Cheers, and hth.,

- Alf

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
.

Relevant Pages