We could do all this and bound the number of linking steps by n.
The above analysis will not help when we try to analyze a sequence of operations that include more than just insertions.
Consider the result of an insertion.
|ti + (ci - ci - 1) =||2|
|ai||=||ti + (ci - ci - 1)|
|ti||=||ai - (cn - c0)|
|=||2n - (cn - c0)|
As long as (cn - c0) is positive, we are done.
In any case (cn - c0) is bounded by log n if we start with an empty tree.
Assume that the two queues to be merged have n1 and n2nodes with T1 and T2 trees. Let n = n1+ n2. Actual time to perform merge is given by:
|ti||= 0(logn1 + logn2)|
|= 0(max(logn1, logn2)|
|= 0(log n)|