-
Consider the following operation along the Enqueue and Dequeue operations on queues, where k is a global parameter. Multi-Dequeue(Q){ m = k while (Q is not empty) and (m > 0){ Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of n queue operations on an initially empty queue ?
-
- Θ(n)
- Θ(n + k)
- Θ(nk)
- Θ(n2)
- Θ(n)
Correct Option: A
To compute the worst case time complexity of a sequence of n queue operations on an initially empty queue is θ(n).
Complexity of a squence of 'n' queue operations = Total complexity of Enqueue operations (α) + Total complexity of Dequeue operations (β).
Total complexity of Dequeue operations (β) ≤ Total complexity of Enqueue operations
β ≤ α ...(i)
Total complexity of queue operations (α) ≤ n ...(ii)
Total complexity of n operations = α + β
≤ α + α [From ...(i)]
≤ n + n [From... (ii)]
≤ 2 n
∴ Worst Case Time Complexity of 'n' operations is (a) θ(n).
