<p>There are two ways to analyze this: worst-case and average-case.  In the worst case, an adversary can always direct an incoming element to the shortest gap or longest gap-free region.  After an initial O(log n) time, all further insertions take O(n) time each.</p>
<p>Things are a little better in the average case, but still get slow after a while.  The problem with this approach is that the gaps do not remain well-distributed.  Call a region of the array with no gaps a “block”.  When a new element needs to be inserted in a block, half the block has to be moved.  So we need to avoid long blocks.  Unfortunately, the longer a block, the more likely an incoming element is to land inside it.  So long blocks tend to get longer.  Even worse, a block can absorb the following block if there is only one space between them.  So blocks tend to grow much faster than you might imagine.</p>
<p>This is called “primary clustering” in a hash table with “linear probing”.  The growth of the blocks was analyzed by Knuth, in a very neat application of analytic combinatorics.  Unfortunately I can’t find the reference.</p>

CC BY-SA 4.0
2022-06-01T08:42:23.827Z
Hi!
Yes, Knuth's analysis of linear probing is what gave me the idea. As mentioned on the Wikipedia page on linear probing, Knuth proved that assuming that the empty spaces take up a constant percentage of the array, the operations take constant time on average. That is, primary clustering turns out not to be a problem.
Zur Luria
CC BY-SA 4.0
2022-06-01T09:23:47.860Z
One addition to the "worst case analysis" above. For hashes, we can suppose that the insertion arrive randomly and therefore the average case makes sense but for BST, it is generally not true: on many practical cases you have to insert long chains of increasing or decreasing sequence or even consecutive elements.
Louis
CC BY-SA 4.0
2022-06-01T09:27:44.167Z
Sorry for the double comment but a second addition to the worst case analysis: when  inserting/deleting from an array that is not full enough you will spend a lot of time searching for an element to compare with during the binary search tree. For instance inserting into an empty array takes O(n) because you have to check that it is empty.
Louis
CC BY-SA 4.0
2022-05-31T14:16:28.790Z
2022-05-31T14:18:11.567Z
2022-05-31T14:18:11.567Z
user36447
<p>There are many data structures that have O(log(n)) insert, delete and find operations: Self balancing binary search trees, skip lists and others. My question is: Why doesn't the following simple thing work?</p>
<p>Just hold an array whose values are sorted, with a certain percentage of <strong>empty cells</strong> distributed in a randomish way over the length of the array.
For example,
<span class="math-container">$$
A = [1, -, -, 2, 3, -, 5, -, 7]
$$</span></p>
<ul>
<li>Find is the usual binary search, where if you hit an empty cell you go right until you find a value.</li>
<li>To delete, you find the value you want to delete and then delete it.</li>
<li>To insert, you find the place where your new element is supposed to go using binary search, and then insert it, moving elements to the right if an empty space needs to be created.</li>
</ul>
<p>I haven't done the analysis, but it seems like this should provide O(log(n)) average case runtime for the different operations, just like a binary search tree. Is there a name for this thing? Do people use it?</p>

CC BY-SA 4.0
2022-05-29T08:56:56.323Z
I think this is basically https://en.wikipedia.org/wiki/Library_sort
Emil Jeřábek
CC BY-SA 4.0
2022-05-29T09:13:03.020Z
Thank you! Yes, that seems to be it. I'll go read the paper.
Zur Luria
CC BY-SA 4.0
2022-05-30T05:33:16.887Z
Note the comment “ If used without this shuffling, it could easily degenerate into quadratic behaviour.” This seems to suggest that their methods (as stated) don’t (directly) generalize to a data structure (since it requires to see the *whole* input in advance to shuffle it)
daniello
<ds.data-structures>
Alternative to binary search trees: A sorted array with empty spaces
Zur Luria
# Alternative to binary search trees: A sorted array with empty spaces

(Asked by: username_0 on 2022-05-29)

There are many data structures that have O(log(n)) insert, delete and find operations: Self balancing binary search trees, skip lists and others. My question is: Why doesn't the following simple thing work?

Just hold an array whose values are sorted, with a certain percentage of **empty cells** distributed in a randomish way over the length of the array.
For example,
$$
A = [1, -, -, 2, 3, -, 5, -, 7]
$$

* Find is the usual binary search, where if you hit an empty cell you go right until you find a value.
* To delete, you find the value you want to delete and then delete it.
* To insert, you find the place where your new element is supposed to go using binary search, and then insert it, moving elements to the right if an empty space needs to be created.

I haven't done the analysis, but it seems like this should provide O(log(n)) average case runtime for the different operations, just like a binary search tree. Is there a name for this thing? Do people use it?

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: I think this is basically https://en.wikipedia.org/wiki/Library_sort  
> **username_0**: Thank you! Yes, that seems to be it. I'll go read the paper.  
> **username_2**: Note the comment “ If used without this shuffling, it could easily degenerate into quadratic behaviour.” This seems to suggest that their methods (as stated) don’t (directly) generalize to a data structure (since it requires to see the *whole* input in advance to shuffle it)  

---

## 1 answers

### Answer by username_3 on 2022-05-31. Score: 1

There are two ways to analyze this: worst-case and average-case. In the worst case, an adversary can always direct an incoming element to the shortest gap or longest gap-free region. After an initial O(log n) time, all further insertions take O(n) time each.

Things are a little better in the average case, but still get slow after a while. The problem with this approach is that the gaps do not remain well-distributed. Call a region of the array with no gaps a “block”. When a new element needs to be inserted in a block, half the block has to be moved. So we need to avoid long blocks. Unfortunately, the longer a block, the more likely an incoming element is to land inside it. So long blocks tend to get longer. Even worse, a block can absorb the following block if there is only one space between them. So blocks tend to grow much faster than you might imagine.

This is called “primary clustering” in a hash table with “linear probing”. The growth of the blocks was analyzed by Knuth, in a very neat application of analytic combinatorics. Unfortunately I can’t find the reference.

> **Comments:**
> **username_0**: Hi! Yes, Knuth's analysis of linear probing is what gave me the idea. As mentioned on the Wikipedia page on linear probing, Knuth proved that assuming that the empty spaces take up a constant percentage of the array, the operations take constant time on average. That is, primary clustering turns out not to be a problem.  
> **username_4**: One addition to the "worst case analysis" above. For hashes, we can suppose that the insertion arrive randomly and therefore the average case makes sense but for BST, it is generally not true: on many practical cases you have to insert long chains of increasing or decreasing sequence or even consecutive elements.  
> **username_4**: Sorry for the double comment but a second addition to the worst case analysis: when  inserting/deleting from an array that is not full enough you will spend a lot of time searching for an element to compare with during the binary search tree. For instance inserting into an empty array takes O(n) because you have to check that it is empty.  

---

