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

[=?utf-8?B?5YiY5piK?=]

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

Best regards

[Daniel Kraft]

>Hi, folks,

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

Yes.

How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).

And first, you will have to find it (if I understood your question
correctly), which takes O(log n) for a sorted array.

Cheers,
Daniel

--
Got two Dear-Daniel-Instant Messages
by MSN, associate ICQ with stress--so
please use good, old E-MAIL!

[Daniel Kraft]

>Deleting from any array (sorted or not) takes O(n) except when

>deleting from the end or the beginning.

Sorry, that's incorrect. That depends on the definitions of "delete",
"array", "end", "beginning". In particular, no C++ implementation where
"delete" takes linear time, would be widely used. Also, in the more
general context of computer programming, I think you suffer from the
misconception that general array insertion and deletion is necessarily
O(n), as compared to linked list operations. That is simply incorrect;
you might want to look up cursor gap structures somewhere.

I suppose the OP meant "removing" or "erasing" or whatever a single
element from inside the array, which has nothing to do with C++'s delete
(but of course I could have misunderstood the original question).

And as I understood it, he actually means "an array in C++", which is
something like
int foo[256];

which *has* characteristics similar to a std::vector, and which
*requires* O(n) for insertion and removing of elements in the middle.
If the OP was interested in special, optimized data-structures other
than arrays, he would have stated (I believe).

>And first, you will have to find it

Why, and what? That is an extra requirement, not mentioned before now.

The element, or so to say: I thought the OP wants to delete a element
in the array which equals some value he has stored. Therefore, he first
needs to "find" that element in the array, that is, and iterator
pointing to it.

If you want help with that new problem, please describe it accurately
and point out why you consider the question to be on-topic in [clc++].
And I don't understand why I should have to find your array for you, or
perhaps it is the OP's array I "have to" find. That's just silly.

Yes, that's true. However, it was not me to post this question here.

Rgds,
Daniel

[Kai-Uwe Bux]

Alf P. Steinbach wrote:

* Daniel Kraft:

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

Yes.

How that?

Any way you like, as long as it's O(1): the only correct answer to the
OP's question -- not amended as you see fit -- is "yes".

>Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning.

Sorry, that's incorrect. That depends on the definitions of "delete",
"array", "end", "beginning". In particular, no C++ implementation where
"delete" takes linear time, would be widely used. Also, in the more
general context of computer programming, I think you suffer from the
misconception that general array insertion and deletion is necessarily
O(n), as compared to linked list operations. That is simply incorrect;
you might want to look up cursor gap structures somewhere.

Interesting idea. I read about cursor gap structures when I researched how
to implement text buffers for, but I do not see how they apply to the
problem. As far as I can see, cursor gap structures are well suited if
insertions and deletions have a certain degree of locality (i.e., they
occur in nearby places). But I do not see how one can use this technique to
implement a data structure with constant time random access by index and
constant time entry removal (note that if the structure already has a gap
and the removal happens at a far away place, one would need to move the gap
first).

Could you be a little more specific or provide a reference about how to do
O(1) deletion using a cursor gap?
Best

Kai-Uwe Bux

[tom]

On Aug 19, 1:43 am, Kai-Uwe Bux <[e-mail]:

Alf P. Steinbach wrote:

* Daniel Kraft:

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

>Yes.

How that?

Any way you like, as long as it's O(1): the only correct answer to the
OP's question -- not amended as you see fit -- is "yes".

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning.

Sorry, that's incorrect. That depends on the definitions of "delete",
"array", "end", "beginning". In particular, no C++ implementation where
"delete" takes linear time, would be widely used. Also, in the more
general context of computer programming, I think you suffer from the
misconception that general array insertion and deletion is necessarily
O(n), as compared to linked list operations. That is simply incorrect;
you might want to look up cursor gap structures somewhere.

Interesting idea. I read about cursor gap structures when I researched how
to implement text buffers for, but I do not see how they apply to the
problem. As far as I can see, cursor gap structures are well suited if
insertions and deletions have a certain degree of locality (i.e., they
occur in nearby places). But I do not see how one can use this technique to
implement a data structure with constant time random access by index and
constant time entry removal (note that if the structure already has a gap
and the removal happens at a far away place, one would need to move the gap
first).

Could you be a little more specific or provide a reference about how to do
O(1) deletion using a cursor gap?

Best

Kai-Uwe Bux- Hide quoted text -

- Show quoted text -

To delete an array, you got to:
1. locate it and get a handle(iterate, referece, pointer etc) to it.
(time: log n)
2. delete it by moving the elements after it one position ahead.
(time: n)

To achiveve your goal, you may want to use the associate containers
like: multiset

[red floyd]

Daniel Kraft wrote:

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

Yes.

How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).

[NITPICKY-SMARTALECKY]
OP didn't specify *any* element, he specified *an* element. So yes, in
any array, there exists an element which can be deleted from a sorted
array in O(1) time (namely the last one).
[/NITPICKY-SMARTALECKY]

[Kai-Uwe Bux]

red floyd wrote:

Daniel Kraft wrote:

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

Yes.

How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).

[NITPICKY-SMARTALECKY]
OP didn't specify *any* element, he specified *an* element. So yes, in
any array, there exists an element which can be deleted from a sorted
array in O(1) time (namely the last one).
[/NITPICKY-SMARTALECKY]

Similarly: since the OP asked about "a sorted array" as opposed to "any
sorted array", one might as well observe that there are sorted arrays
(e.g., those that consist of identical values) from which _each_ element
can be removed in constant time. <g>

However, it seems a far-fetched assumption that the OP wanted to know
whether there exists some sorted arrays from which at least one element
could be removed in constant time.
Best

Kai-Uwe Bux

[Diego Martins]

this is the most clueless topic I've seen here