3
$\begingroup$

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 queue operations on an initially full  queue having n elements.?  

(A) $\Theta(n) $ 

(B) $\Theta(n+k)$

(C) $\Theta(nk)$

(D) $\Theta(n^2)$


Here suppose we do one dequeue operation, then the loop will run for min(n,k) times. Now remaining 1 operation can be 1 enqueue operation which will take O(1) time so total complexity in this case will be O(min(n,k)).

Suppose we have k=1 and do (n-1) dequeue operations then it will take k*(n-1) time for multideqeue function and remaining one enqueue operation will take O(1) time . So in total we are getting O(kn) time in this case.

I am confused on how to handle 'k' parameter when we are calculating complexity.

NOTE :- n queue operations can be any combination of enqueue/dequeue/multi-dequeue(as defined) operation.

Any help would be appreciated.

$\endgroup$
1
  • $\begingroup$ @Dukeling You can assume it n. I will include it in the question. $\endgroup$ – Zephyr Dec 24 '17 at 12:29
2
$\begingroup$

It's $\Theta(n)$. Observe that if you are limited by $n$ operations, the total number of elements that ever enter the queue is less than or equal to $n$. Furthermore, every element is processed at most twice: once when it enters the queue, and once when it leaves the queue, therefore the total time is at most a constant times $n$.

$\endgroup$
7
  • $\begingroup$ Also why is $\Theta(n+k)$ not the correct answer? $\endgroup$ – Zephyr Dec 24 '17 at 5:37
  • $\begingroup$ If at the beginning I perform 1 multi-D operation with k=n then it will take O(n) time. Now 'n-2' enqueue operations will take O(n-2) time. Now again 1 multideqeue operation will take O(n-2) time. So total O(3n-4). $\endgroup$ – Zephyr Dec 24 '17 at 6:13
  • $\begingroup$ The $k$ parameter is irrelevant to the complexity. Also, $\Theta(3n-4) = \Theta(n)$, I suggest you review the Landau notation. $\endgroup$ – quicksort Dec 24 '17 at 8:42
  • $\begingroup$ I know that constants are irrelevant in landau notation. Wouldn't $\Theta(n+k)$ be more precise ? $\endgroup$ – Zephyr Dec 24 '17 at 8:45
  • $\begingroup$ No. $k$ is irrelevant. $\endgroup$ – quicksort Dec 24 '17 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.