6
$\begingroup$

I'm trying to come up with a data structure that could access, insert, and delete any element in constant time. I know that's pretty difficult, but I'm just doing it to invoke thought and understanding about computer science. However, I'm starting to question whether it is even possible.

My theory is: For access to be in constant time, the data would need to be stored in a static location (like an array). And for insertion/deletion to be in constant time, the data would need to be stored dynamically using pointers or some sort of lookup table (like a linked list). Therefore, no data structure can have all three operations run in constant time.

Is this reasoning correct?

EDIT:

access(index): returns element at given index

insert(element, index): Inserts element into 'index' and shifts everything after 'index' right one index

delete(index): Removes element at 'index' and corrects indexes so that there are no gaps (i.e. shifts everything after 'index' left one index)

Improve this question
$\endgroup$
1
  • $\begingroup$ See also this question. Note that the requirements are slightly different, they use 'insertAfter' instead of 'insert', whatever the difference is. $\endgroup$
    – TilmannZ
    Commented Apr 27, 2018 at 8:28

3 Answers 3

Reset to default
2
$\begingroup$

How do we get lower bounds?

As D.W. noted, lower bounds are hard. But that doesn't mean that no progress can be made. To get a lower bound, it is required (well, not strictly, but you won't get very far without one) that you make a (possible restrictive) model of all algorithms or data-structures that can solve your problem.

For example, the $\Omega(n\log n)$ lower bound for sorting holds only for the restrictive 'comparison based sorting' algorithms. (this is why counting sort can 'beat' this time in some cases: it isn't comparison based)

Lower bounds for data structures

For the case of data-structures, the cell-probe model seems a good place to start. This model is similar to the more common RAM-model, but can be useful for lower bounds as it 'only counts' the number of accesses to stored data (i.e. the number of 'probes' to a cell).

For example, in the paper by Yao that introduces this model, lower bounds are calculated for the data structure supporting INSERT, DELETE and MEMBER (test for membership) queries. I think that a similar technique could work for your data-structure as well.

Do note that the paper by Yao is a bit outdated. I mostly mentioned it because the problem it considered is relatively simple and similar to yours. More modern techniques are covered in the dissertation of Kasper Green Larsen.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much! Those references seem very useful. I'll research everything tonight. $\endgroup$
    – Badr B
    Commented Apr 29, 2018 at 15:57
  • 1
    $\begingroup$ @BadrB You're welcome. I'd be interested in seeing a proof that constant time for all operations is impossible, if you manage to find one. In that case, I suggest you add that here as an answer to your own question. In case you encounter some specific difficulty with these texts or in proving a lower bound, feel free to ask another question about those. $\endgroup$
    – Discrete lizard ♦
    Commented Apr 29, 2018 at 16:47
0
$\begingroup$

I don't find the reasoning convincing. Perhaps there is some other way to do it you haven't imagined yet. Proving lower bounds is hard.

That said, I doubt that it's possible to support all three operations in $O(1)$ time, though I don't have a proof.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the insight. I think I'll spend more time trying to prove/disprove its existence rather than just trying to come up with such a data structure lol. I think that'll be the best bet to conquer this tough task. $\endgroup$
    – Badr B
    Commented Apr 26, 2018 at 23:31
0
$\begingroup$

It have been prooven, that what you expect is not possible, the lower bound is somewhere like $\Omega{\left( \frac{\log n}{\log \log n} \right)} $ (see here, like TillmanZ already pointed out).

However, hashing gives very fast lookup (somewhere like $\mathcal{O} (1) $ in general). The so-called Cuckoo-hashing guarantees constant lookup and expected constant insert time (amortized). Deletion normally is not considered but it can be done really simply by lookup and clearing the value, resulting also in $\mathcal{O} (1) $.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Cuckoo hashing doesn't support the operations listed here. Take another look at the desired semantics of insert (and delete). This makes me wonder whether the result you mention applies to these operations too. $\endgroup$
    – D.W. ♦
    Commented May 6, 2018 at 20:03
  • $\begingroup$ There is a difference in the requirements of data-structure in the question you reference and this question: in the data-structure here, elements are accessed by their index, not by some pointer we somehow know. The other DS can simulate the one from this question, but for the lower bound to hold here it would be required that this DS can simulate the other. I don't see how to do that immediately. Perhaps a minor modification to the proof of the lower bound would do the trick. At the very least, I'm not convinced that this lower bound is directly relevant here. $\endgroup$
    – Discrete lizard ♦
    Commented May 7, 2018 at 8:34
  • $\begingroup$ @D.W. Yes, you are right, the operations are slightly different. Especially insert would not shift the indices of following elements (so you do not have indices but keys). However, i wanted to mention that constant insert AND lookup is possible, since many people get stuck at $\log {n}$, either for lookup or for insert. $\endgroup$
    – Dániel Somogyi
    Commented May 11, 2018 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.