in DS edited by
1,241 views
0 votes
0 votes

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

  1. $O(n),O(n)$
  2. $O(n),O(1)$
  3. $O(1),O(n)$
  4. $O(1),O(1)$
in DS edited by
1.2k views

2 Answers

1 vote
1 vote

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/

 

 

0 votes
0 votes
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).
Answer:

Related questions