×

# Confusion in complexity of buidling a merge sort tree

 0 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)? asked 22 Mar '18, 12:35 3★adzo261 289●8 accept rate: 37%

 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})$$ answered 22 Mar '18, 13:47 825●1●12 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,727
×699
×145
×141
×74
×28
×14

question asked: 22 Mar '18, 12:35

question was seen: 168 times

last updated: 22 Mar '18, 13:47