PrepSnap logoPrepSnap
Pass

Question

1.
2.
3.
4.
Answer (Detailed Solution Below)

Option 3 : O(1) amortised, because each element moves between stacks at most twice / O(1) परिशोधित, क्योंकि प्रत्येक अवयव स्टैकों के बीच अधिकतम दो बार चलता है

Advertisement

Detailed Solution

सही उत्तर O(1) amortised, because each element moves between stacks at most twice / O(1) परिशोधित, क्योंकि प्रत्येक अवयव स्टैकों के बीच अधिकतम दो बार चलता है है।

Key Points
Helpful?
PrepSnapprepsnap.in • Part -A

Question:

A queue is implemented using two stacks. The amortised time complexity of a dequeue operation is / दो स्टैकों से कतार कार्यान्वित की गई है। dequeue संक्रिया की परिशोधित समय-जटिलता है

1.
O(n) in every case / प्रत्येक स्थिति में O(n)
2.
O(1) in the worst case / निकृष्टतम स्थिति में O(1)
3.
O(1) amortised, because each element moves between stacks at most twice / O(1) परिशोधित, क्योंकि प्रत्येक अवयव स्टैकों के बीच अधिकतम दो बार चलता है
4.
O(n²) due to repeated copying / O(n²), बार-बार प्रतिलिपि के कारण

Correct Answer: O(1) amortised, because each element moves between stacks at most twice / O(1) परिशोधित, क्योंकि प्रत्येक अवयव स्टैकों के बीच अधिकतम दो बार चलता है

Elements are transferred from the input stack to the output stack at most once each, so n dequeues cost O(n) total — O(1) amortised — though a single dequeue can cost O(n) in the worst case. / अवयव इनपुट स्टैक से आउटपुट स्टैक में अधिकतम एक बार स्थानांतरित होते हैं, अतः n dequeue की कुल लागत O(n) — O(1) परिशोधित — हालाँकि एकल dequeue निकृष्टतम में O(n) ले सकता है।

Downloaded from PrepSnap (prepsnap.in)