P: n/a

Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
Best regards  
Share this Question
P: n/a

>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 DearDanielInstant Messages
by MSN, associate ICQ with stressso
please use good, old EMAIL!  
P: n/a

>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 datastructures 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 ontopic 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  
P: n/a

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
KaiUwe Bux  
P: n/a

On Aug 19, 1:43 am, KaiUwe Bux <jkherci...@gmx.netwrote:
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
KaiUwe 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  
P: n/a

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).
[NITPICKYSMARTALECKY]
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).
[/NITPICKYSMARTALECKY]  
P: n/a

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).
[NITPICKYSMARTALECKY]
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).
[/NITPICKYSMARTALECKY]
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 farfetched 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
KaiUwe Bux  
P: n/a

this is the most clueless topic I've seen here   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 4494
 replies: 7
 date asked: Aug 18 '07
