A normal segment tree is a full binary tree and it has n leaf nodes and n1 internal nodes. Hence, 2*n1 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) twopointer merge. We do this for every nonleaf node, so why the overall build complexity of merge sort tree is not O(n*n)? asked 22 Mar '18, 12:35

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})$$ answered 22 Mar '18, 13:47
