Data Structure and Algorithms #6
Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter :
MultiDequeue(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 MultiDequeue() operations on an initially empty queue?
(A) \Theta(n) (B) \Theta(n + k) (C) \Theta(nk) (D) \Theta(n^2)
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Since the queue is empty initially, the condition of while loop never becomes true. So the time complexity is \Theta(n)