2

I am struggling to figure out the time complexity of the following problem (this is not homework, just something I came up with and can't understand).

Suppose you have an arbitrary tree. The algorithm is such that for every node in the tree you have to run some O(1) operation as many times as that node's number of leaf descendants. So, in the example tree below, we would run 2 operations for node A and 6 operations for the root node R.

example tree

Let's say you have n nodes, the tree is of depth d, and you may use any other notation necessary. What is the complexity?

I can't quite wrap my head around this. Surely it is less than O(n^2) but how do I approach this? Thank you!

Edit: leaf descendant of a node is a descendant that does not have any children. A descendant is a node reachable by repeated proceeding from parent to child (doesn't matter if it's an internal or a leaf node)

Improve this question
10
  • Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants of R should be 9? Commented Nov 16, 2018 at 4:30
  • 1
    9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children. Commented Nov 16, 2018 at 4:34
  • The link to the text is uncomfortable to read. Perhaps upload an image to a post Commented Nov 16, 2018 at 4:35
  • Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks! Commented Nov 16, 2018 at 4:36
  • I'm not very good at this stuff but here's my intuition. If you have n nodes, and each node has a corresponding number of leaf descendants d, then the complexity is nd. It's easy to see that d < n so nd < n^2. I don't think you can say anything else without specifying more information about the tree. Commented Nov 16, 2018 at 4:36

2 Answers 2

Reset to default
2

It's Ө(n^2). Obviously, as you noted, it's in O(n^2) because each node must have fewer than n descendant leaves.

In a tree with a construction like this:

     A
    /  \
   B    C
       / \
      D   E
         / \
        F   G
             ...

The top-most n/4 internal nodes have at least n/4 descendant leaves, so the total number of operations is at least n^2/16, which is in Ω(n^2).

If you have a depth limit d, then each node can have at most d ancestors, so you get O(n*min(d,n)), which is also tight by a similar construction.

Improve this answer
Sign up to request clarification or add additional context in comments.

18 Comments

I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
No. In the constructed tree, n/2 of the nodes are leaves, and the other n/2 nodes are internal nodes. The top-most n/4 internal nodes have n/4 leaf children, and the remaining n/2 nodes in the whole tree are in the right child of the last one. Half of those, or n/4 nodes, are leaves. Those leaves are all descendants of every one of the top-most n/4 internal nodes.
Also, if a node has at most d ancestors, it doesn't mean that it will have at most d leaf descendants, right? What am I missing here? (Sorry I am not good with complexity stuff, please bear with me)
That's right, but the number of (node,descendant) pairs, which is the total number of operations, is sum(ancestors of each leaf) AND sum(leaf descendents of each node) -- those come out to the same number.
@billyb With d being fully constraint, I mean that you consider only trees with fixed d (but d possibly dependent on n) for the worst-case analysis. For example if d is supposed to always be maximal, then there is only one tree with this property, the linear chain, for which the time complexity is O(n), not O(n^2) because it has only one leaf. If however you allow tree with any d as input, then there are trees such that the wort time complexity is O(n^2) (in particular for d growing proportionally with n and proportionality factor strictly between 0 and 1).
|
0

I think it will be O(2(N - Leaf) + Leaf) where Leaf is the number of descendants of the tree. O(2(N - Leaf)) is required to iterate over the tree to find the leaf descendants and a O(1) operation needs to be performed on each of them.

Improve this answer

1 Comment

As you were told in another comment, the operation per node is not O(1), but O(leaf descendants). Furthermore what would descendants of the tree be? Usually descendants is a property of a node. O(2(...)) is identical to O(...) and would usually written in this shorter way and 2(N-Leaf)+Leaf is just 2N-Leaf.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.