-1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think this is basically en.wikipedia.org/wiki/Library_sort $\endgroup$
    – Emil Jeřábek
    May 29, 2022 at 8:56
  • $\begingroup$ Thank you! Yes, that seems to be it. I'll go read the paper. $\endgroup$
    – Zur Luria
    May 29, 2022 at 9:13
  • 1
    $\begingroup$ 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) $\endgroup$
    – daniello
    May 30, 2022 at 5:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Zur Luria
    Jun 1, 2022 at 8:42
  • $\begingroup$ 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. $\endgroup$
    – Louis
    Jun 1, 2022 at 9:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Louis
    Jun 1, 2022 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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