By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,905 Members | 2,064 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,905 IT Pros & Developers. It's quick & easy.

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

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

Best regards

Aug 18 '07 #1
Share this Question
Share on Google+
7 Replies


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 Dear-Daniel-Instant Messages
by MSN, associate ICQ with stress--so
please use good, old E-MAIL!
Aug 18 '07 #2

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 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
Aug 18 '07 #3

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

Kai-Uwe Bux
Aug 18 '07 #4

P: n/a
tom
On Aug 19, 1:43 am, Kai-Uwe 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

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

Aug 18 '07 #5

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).
[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]
Aug 18 '07 #6

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).

[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
Aug 19 '07 #7

P: n/a
this is the most clueless topic I've seen here

Aug 20 '07 #8

This discussion thread is closed

Replies have been disabled for this discussion.