Jim_Moriarty_'s blog

Time complexity of building of merge sort tree

By Jim_Moriarty_, history, 7 years ago, In English

Can anyone explain !! How the complexity of building the merge sort is O(nlog(n)) . As if we build segment tree for maximum query it will take O(n) time because we had to cover approx 2*n to 4*n nodes and at each node merging two children nodes took O(1) time. But here in merge sort merging two children nodes takes O(n) time . So how come the complexity is O(nlog(n))?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
16 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Merging two children's time complexity is $$$O(n)$$$, while $$$n$$$ is the number of values.

If we draw the merge sort tree (like a binary tree), we can see that we have $$$n$$$ values in each level; because in the first level we have all elements in one node ($$$n$$$ elements), in the second level we divide them (but they still $$$n$$$!).

We have $$$log_2(n)$$$ levels, every level has $$$n$$$ values, then we have $$$n \cdot log_2(n)$$$ values, we iterate over them in $$$O(n \cdot log_2(n))$$$ time complexity.

If you need any clarify, feel free to ask and I will answer <3

→ Reply