CODEWITHSUNDEEP
algorithmsortingqueuetime-complexityimplementation
Adam Staples
Adam Staples

Reputation: 406

Time complexity/performance of insertion operation for a Queue implementation (In java)

What is the performance of the insertion operation for a Queue implemented as:

(a) an array, with the items in unsorted order

(b) an array, with the items in sorted order

(c) a linked list, with the items in unsorted order.

For each operation, and each implementation, give the performance in Big Oh notation and explain enough of the algorithm to justify your answer. (e.g. it takes O(n) times because in the worse case.... the algorithm does such and such....).

Please explain in detail, it'll help me out a lot!

Upvotes: 0

Views: 7177

Answers (1)

Jason Baker
Jason Baker

Reputation: 2483

Short answer: it depends on your data structure.

In a naive array-based implementation (Assuming fixed size), I think it's pretty obvious that insertion is a constant operation (That is, O(1)), assuming that you don't run off the end of the array. This is similar in a cyclic array, with similar assumptions.

A dynamic array is a little more complicated. A dynamic array is a fixed-size array that you enlarge once it's filled to a certain point. So for a dynamic array that resizes when it reaches length k, the first k-1 insertions are constant (Just like inserting into an ordinary array) and the k-th insertion takes O(k+1) - the cost of duplicating the contents of the array into a larger container, and then inserting the element. You can show that this works out to O(1) insertion time, but that may be out of scope for your course.

As others have noted, sorted order doesn't affect a standard queue. If you are in fact dealing with a priority queue, then there are lots of possible implementations, which I'll let you research on your own. The best insertion time is O(1), but that implementation has some disadvantages. The standard implementation is O(log n) insertion.

With linked lists, the insertion time will depend on whether the head of the list is the head of the queue (i.e., whether you add onto the head or the tail).

If you're adding onto the head, then it's pretty easy to see that insertion is O(1). If you're adding onto the tail, then it's also easy to see that insertion is O(n) for a list of length n. The main point is that, whichever implementation you choose, insert will always be one of O(1) or O(n), and removal will always be the other.

However, there is a simple trick that will let you get both insert and removal to O(1) in either case. I'll leave it to you to consider how to do that.

Upvotes: 2

Related Questions