Array Implementation of OrderedSet

We want to efficiently implement the OrderedSet ADT with an array as the underlying data structure.

Exercise Complete the following table.

OperationHow?Runtime
has
insert
remove
size
Solution

Except for size, all operations require a helper find method to check if an element exists. Then, we can perform Binary Search, so find and has will cost $O(\lg n)$. The insert and remove operations will remain linear since we must shift the elements around to keep the values in order.

OperationHow?Runtime
hasreturn find(t) != -1;$O(\lg n)$
insertFind where to insert, then shift elements to make room.$O(n)$
removeFind the element, shift all element after it to left.$O(n)$
sizereturn numElements;$O(1)$
findBinary search$O(\lg n)$

We leave this as an (unsolved) exercise to you: implement the operations of an array-based OrderedSet.