NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 12

Question

If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?

• A. $O(n),O(n)$
• B. $O(n),O(1)$
• C. $O(1),O(n)$
• D. $O(1),O(1)$

Answer 1

You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail.

From which we can conclude that the time complexity is O(1).

For dequeing, we only need to set the next node of the current head as the new head and return the value of the old head.

From which we can conclude that the time complexity is O(1).

Time complexity of all operations like enqueue(), dequeue(), isFull(), isEmpty(), front() and rear() is O(1). There is no loop in any of the operations.

https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/

 

 

Answer 2

Option C :

Inserting element : Insert at last O(1),

Removing element : Delete from first (O(1) + O(n)[shifting n elements 1 step ahead]) = O(n).