Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

checknmate's blog

By checknmate, 2 days ago, In English

Why do we assume the time complexity of any divide and conquer approach to be the number of level the tree has, should not it be the total edges in tree, like in case of merge sort we have logN, (not including the O(N) of merge since I had doubt regarding the tree).

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

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any genuine help by codeforcers ?

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in devide and conquer you always traverse down the tree (from parent to one of the children) you never go from a child to a parent .And you stop when there no more children.

    That's what it means to traverse the levels of a tree .

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I assume you're referring to tree divide/centroid decomposition.

The tree divide is based on you can process a vertex in O(n) time, where n is the size of the subtree. By selecting centroid every time, you can effectively cut down the size of the subtree.

The worst case of tree divide is when the tree is a link. You find the centroid and break the link into two n2 links, and then four n4 links, eight n8 links and so on. That is to say, we have O(n+2n2+4n4+) complexity. Since each link represents a vertex, the 1+2+4+ term should be equal to n, so we have Θ(logn) terms in the complexity formula, and each term is equal to n, so we have a O(nlogn) complexity.