Algorithms Complexity – Are Constant Time and Amortized Constant Time Equivalent

algorithmscomplexity

I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).

My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have constant access via an index.

Looking over the documentation though, I realized that ArrayLists' additions are considered Amortized Constant Time, since an addition may require a reallocation of the underlying array, which is O(n).

Are Amortized Constant Time and Constant Time effectively the same, or do I need to look at some structure thay doesn't require a full reallocation on every addition?

I'm asking this because array based structures aside (which as far as I know will always have Amortized Constant Time additions), I can't think of anything that will meet the requirements:

  • Anything tree based will have at best O(log n) access
  • A linked list could potentially have O(1) additions (if a reference to the tail is kept), but a random removal should be at best O(n).

Here's the full question; in case I glazed over some important details:

Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The add(x) and remove() operations in a RandomQueue should run in constant time per operation.

Best Answer

Amortized Constant Time can almost always be considered equivalent to Constant Time, and without knowing the specifics of your application and the type of usage you are planning to do to this queue, most chances are that you will be covered.

An array list has the concept of capacity, which is basically equal to the largest size/length/count of items that has ever been required of it thus far. So, what will happen is that in the beginning the array list will keep reallocating itself to increase its capacity as you keep adding items to it, but at some point the average number of items added per unit time will inevitably match the average number of items removed per unit time, (otherwise you would eventually run out of memory anyway,) at which point the array will stop reallocating itself, and all appends will be met at constant time of O(1).

However, keep in mind that by default, random removal from an array list is not O(1), it is O(N), because array lists move all the items after the removed item one position down to take the place of the removed item. In order to achieve O(1) you will have to override the default behavior to replace the removed item with a copy of the last item of the array list, and then remove the last item, so that no items will be moved. But then, if you do that, you do not exactly have a queue anymore.

Related Topic