Confusion in complexity of buidling a merge sort tree

general
, , , , , ,
1

A normal segment tree is a full binary tree and it has n leaf nodes and n-1 internal nodes.
Hence, 2*n-1 nodes in total.
So, for building a segment tree, the value of every node is calculated once so complexity is O(n).

But for a merge sort tree, we combine the sorted vectors from current node’s left and right child using O(n) two-pointer merge. We do this for every non-leaf node, so why the overall build complexity of merge sort tree is not O(n*n)?

2

To merge left and right child you do consume O(n) time but it’s not always a tight bound.

For example at root you need O(n) time but at it’s child you need O(n/2) time ( though you can say it’s also O(n) but that’s not a tight bound)

The equation for time is

T(n) = 2T(n/2) + O(n)
T(n) = O(n + 2.\frac{n}{2} + 4.\frac{n}{4}...........)
T(n) = O(n + n + ......... + n)

where n comes inside \log{n} times.

So, the time complexity

T(n)= O(n\log{n})
2 Likes