What is the amortized efficiency of skew merge?

Category: QuestionsWhat is the amortized efficiency of skew merge?
Editor">Editor Staff asked 4 weeks ago

What is the amortized efficiency of skew merge?
 
(a) O(N)
 
(b) O( log N)
 
(c) O( N log N)
 
(d) O(N^2)
 
Question is from Heap in chapter Heap of Data Structures & Algorithms I
 
This question was posed to me during an interview for a job.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct option is (b) O( log N)
 
The best explanation: The amortized efficiency of a skew heap is mathematically found to be O( log N).