checknmate's blog

Time complexity in Divide and Conquer Approach
By checknmate, 24 hours 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

»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Any genuine help by codeforcers ?

→ Reply
  • »
    »
    23 hours 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 .

    → Reply
»
22 hours 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 $$$\frac{n}{2}$$$ links, and then four $$$\frac{n}{4}$$$ links, eight $$$\frac{n}{8}$$$ links and so on. That is to say, we have $$$O\left(n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+\cdots\right)$$$ complexity. Since each link represents a vertex, the $$$1+2+4+\cdots$$$ term should be equal to $$$n$$$, so we have $$$\Theta(\log n)$$$ terms in the complexity formula, and each term is equal to $$$n$$$, so we have a $$$O(n\log n)$$$ complexity.

→ Reply