Imagine we have an infinite array, where we store integers. When n
elements are in the array, only n
first cells are used, the rest is empty.
I'm trying to come up with a data structure / algorithm that is capable of:
Each operation has to be in O(sqrt(n))
.
I've come across this site, where the following algorithm was presented:
Unfortunately, this solution is O(sqrt(n) * log(n))
.
How to make it pure O(sqrt(n))
?
Since all the operations require the lookup to be performed, I imagine that inserting and deleting would both be O(1)
. Just a guess. And probably once inserting is done, deleting will be obvious.
What does the infinite array mean?
Basically, you can store any number of elements in it. It is infinite. However, there are two restrictions. First - one cell can only store one element. Second - when the array stores currently n elements, only n first cells can be used.
What about the order?
It does not matter.
Have you considered a bi-parental heap (aka: BEAP)?
The heap maintains a height of sqrt(n)
, which means that insert, find, and remove all run in O(sqrt(n))
in the worst case.
These structures are described in Munro and Suwanda's 1980 paper Implicit data structures for fast search and update.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With