Consider an Array $A$ with $n$ values and the following operations:

  1. get(i): Returns the value of $A[i]$
  2. insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the end of the array)
  3. delete (x) delete the element $A[x]$

What is the best known (amortized) time complexity of all operations? Especially the delete-op seems like it needs at least $\Omega(log n)$

See also the papers in this post. However the insert operation is defined slightly different by me, does this have any effect?

  • 1
    $\begingroup$ Can you be more precise about what should the insert operation do ? Do you just want to insert a value x in the data structure, or do you want to specify where to put it ? Similarly, for delete , do you delete an element or a position ? $\endgroup$ – GBat Jun 6 '19 at 8:16
  • $\begingroup$ Insert should just insert the value into any free place of the array, no more conditions have to be satisfied. For delete we want to delete the element that has to position x (0 indexed) from the array. $\endgroup$ – Panzerkroete Jun 6 '19 at 8:40
  • $\begingroup$ When you say A[i], do you want the element that has rank $i$ in A, or the element which was inserted at $i$ (i.e. insert returned $i$) ? $\endgroup$ – GBat Jun 6 '19 at 9:43
  • $\begingroup$ Like GBat, i hardly understand your insert/delete requirement. What do you ever call a "free place" ? Can you just give an example of a structure that do that even in a high time complexity ? $\endgroup$ – Optidad Jun 6 '19 at 14:52

Ok so I think you can build a structure that has $O(1)$ (amortized) complexity for all operations, and using $O(n)$ space for $n$ insertions.

The underlying array is a dynamic array (let's call it $T$) : it has amortized O(1) complexity for insertion at the end. In the array, you store tuples of values and booleans : the boolean will be set to false when you delete, true when you insert. You also keep a stack / queue / some dynamic data structure with O(1) push and pop to keep the indexes of empty places in the array that were previously filled (i.e. they are not at the end of the array), let's call it $S$.

get(i) : if the boolean at i is true, return the elemet at position $i$ in $T$ : $O(1)$, otherwise return an error : no element at that position.
Insert(x) : if $S$ is empty, insert the element at the end (setting the associated boolean to 1) : $O(1)$ amortized with dynamic array. If $S$ is not empty : pop a position from $S$ and insert the element at that position : $O(1)$ as well.
Delete(i) : set the boolean at $i$ to false, and add $i$ to $S$. $O(1)$ as well.

The only downside of that method is that the array is never reduced, and therefore has size $O$(number of insertions) and not $O$(number of element).

| cite | improve this answer | |

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.