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, 2017 at 12:29

1 Answer 1

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, 2017 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, 2017 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, 2017 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, 2017 at 8:45
  • $\begingroup$ No. $k$ is irrelevant. $\endgroup$
    – quicksort
    Dec 24, 2017 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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