I have a very simple question about the best possible big-O bounds for the following data structure:
It starts out empty When you add an element, it is inserted, and the index it was at is associated with it. So if it was the first item inserted, it's index would be zero:
14 12 19 <- items 0 1 2 <- associated indices
Now if I delete
12 in this instance, the indexes for the other items are updated like so:
14 19 0 1
Adding another element, like 10:
14 19 10 0 1 2
If I were to delete
10 have their indices decreased by one.
In addition to adding and removing elements, you must also be able to search for a specific element and it should tell you what the index of that element is.
What is the tightest possible asymptotic bounds for these methods? Obviously I could do
O(n) for removing elements and make search and add
O(1). However, I was able to use a Fenwick tree to get
O(log(n)) on add, search, and remove. Is it possible to do better than this?