You are not logged in. Please login at www.codechef.com to post your questions!

×

Confusion in complexity of buidling a merge sort tree

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

adzo261's gravatar image

3★adzo261
2898
accept rate: 37%


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})$$

link

answered 22 Mar '18, 13:47

pshishod2645's gravatar image

4★pshishod2645
825112
accept rate: 13%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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