Time complexity of a tree related problem
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.
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)
algorithm data-structures tree time-complexity
asked Nov 16 '18 at 4:05
billybbillyb
135
|
show 5 more comments
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.
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)
algorithm data-structures tree time-complexity
asked Nov 16 '18 at 4:05
billybbillyb
135
Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants ofRshould be 9?
– JiaHao Xu
Nov 16 '18 at 4:30
1
9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children.
– billyb
Nov 16 '18 at 4:34
The link to the text is uncomfortable to read. Perhaps upload an image to a post
– JiaHao Xu
Nov 16 '18 at 4:35
Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks!
– billyb
Nov 16 '18 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.
– Brady Dean
Nov 16 '18 at 4:36
|
show 5 more comments
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.
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)
algorithm data-structures tree time-complexity
asked Nov 16 '18 at 4:05
billybbillyb
135
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.
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)
algorithm data-structures tree time-complexity
algorithm data-structures tree time-complexity
asked Nov 16 '18 at 4:05
billybbillyb
135
asked Nov 16 '18 at 4:05
billybbillyb
135
edited Nov 16 '18 at 5:20
billyb
asked Nov 16 '18 at 4:05
billybbillyb
135
asked Nov 16 '18 at 4:05
billybbillyb
135
asked Nov 16 '18 at 4:05
billybbillyb
135
135
Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants ofRshould be 9?
– JiaHao Xu
Nov 16 '18 at 4:30
1
9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children.
– billyb
Nov 16 '18 at 4:34
The link to the text is uncomfortable to read. Perhaps upload an image to a post
– JiaHao Xu
Nov 16 '18 at 4:35
Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks!
– billyb
Nov 16 '18 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.
– Brady Dean
Nov 16 '18 at 4:36
|
show 5 more comments
Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants ofRshould be 9?
– JiaHao Xu
Nov 16 '18 at 4:30
1
9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children.
– billyb
Nov 16 '18 at 4:34
The link to the text is uncomfortable to read. Perhaps upload an image to a post
– JiaHao Xu
Nov 16 '18 at 4:35
Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks!
– billyb
Nov 16 '18 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.
– Brady Dean
Nov 16 '18 at 4:36
Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants of
R should be 9?– JiaHao Xu
Nov 16 '18 at 4:30
Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants of
R should be 9?– JiaHao Xu
Nov 16 '18 at 4:30
1
1
9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children.
– billyb
Nov 16 '18 at 4:34
9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children.
– billyb
Nov 16 '18 at 4:34
The link to the text is uncomfortable to read. Perhaps upload an image to a post
– JiaHao Xu
Nov 16 '18 at 4:35
The link to the text is uncomfortable to read. Perhaps upload an image to a post
– JiaHao Xu
Nov 16 '18 at 4:35
Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks!
– billyb
Nov 16 '18 at 4:36
Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks!
– billyb
Nov 16 '18 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.
– Brady Dean
Nov 16 '18 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.
– Brady Dean
Nov 16 '18 at 4:36
|
show 5 more comments
2 Answers
2
active
oldest
votes
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.
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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)
– billyb
Nov 16 '18 at 4:53
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.
– Matt Timmermans
Nov 16 '18 at 4:56
1
@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 isO(n), notO(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 isO(n^2)(in particular fordgrowing proportionally with n and proportionality factor strictly between 0 and 1).
– user10605163
Nov 17 '18 at 14:49
|
show 13 more comments
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.
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
As you were told in another comment, the operation per node is notO(1), butO(leaf descendants). Furthermore what woulddescendants of the treebe? Usuallydescendantsis a property of a node.O(2(...))is identical toO(...)and would usually written in this shorter way and2(N-Leaf)+Leafis just2N-Leaf.
– user10605163
Nov 16 '18 at 13:41
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53331284%2ftime-complexity-of-a-tree-related-problem%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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)
– billyb
Nov 16 '18 at 4:53
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.
– Matt Timmermans
Nov 16 '18 at 4:56
1
@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 isO(n), notO(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 isO(n^2)(in particular fordgrowing proportionally with n and proportionality factor strictly between 0 and 1).
– user10605163
Nov 17 '18 at 14:49
|
show 13 more comments
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.
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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)
– billyb
Nov 16 '18 at 4:53
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.
– Matt Timmermans
Nov 16 '18 at 4:56
1
@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 isO(n), notO(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 isO(n^2)(in particular fordgrowing proportionally with n and proportionality factor strictly between 0 and 1).
– user10605163
Nov 17 '18 at 14:49
|
show 13 more comments
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.
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
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.
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
answered Nov 16 '18 at 4:37
Matt TimmermansMatt Timmermans
20.8k11733
20.8k11733
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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)
– billyb
Nov 16 '18 at 4:53
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.
– Matt Timmermans
Nov 16 '18 at 4:56
1
@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 isO(n), notO(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 isO(n^2)(in particular fordgrowing proportionally with n and proportionality factor strictly between 0 and 1).
– user10605163
Nov 17 '18 at 14:49
|
show 13 more comments
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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)
– billyb
Nov 16 '18 at 4:53
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.
– Matt Timmermans
Nov 16 '18 at 4:56
1
@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 isO(n), notO(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 isO(n^2)(in particular fordgrowing proportionally with n and proportionality factor strictly between 0 and 1).
– user10605163
Nov 17 '18 at 14:49
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
I'm not sure I understand the n/4 top nodes/leaves part. Is number 4 arbitrary?
– billyb
Nov 16 '18 at 4:47
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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.
– Matt Timmermans
Nov 16 '18 at 4:49
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)
– billyb
Nov 16 '18 at 4:53
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)
– billyb
Nov 16 '18 at 4:53
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.
– Matt Timmermans
Nov 16 '18 at 4:56
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.
– Matt Timmermans
Nov 16 '18 at 4:56
1
1
@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).– user10605163
Nov 17 '18 at 14:49
@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).– user10605163
Nov 17 '18 at 14:49
|
show 13 more comments
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.
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
As you were told in another comment, the operation per node is notO(1), butO(leaf descendants). Furthermore what woulddescendants of the treebe? Usuallydescendantsis a property of a node.O(2(...))is identical toO(...)and would usually written in this shorter way and2(N-Leaf)+Leafis just2N-Leaf.
– user10605163
Nov 16 '18 at 13:41
add a comment |
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.
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
As you were told in another comment, the operation per node is notO(1), butO(leaf descendants). Furthermore what woulddescendants of the treebe? Usuallydescendantsis a property of a node.O(2(...))is identical toO(...)and would usually written in this shorter way and2(N-Leaf)+Leafis just2N-Leaf.
– user10605163
Nov 16 '18 at 13:41
add a comment |
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.
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
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.
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
answered Nov 16 '18 at 4:54
JiaHao XuJiaHao Xu
687316
687316
As you were told in another comment, the operation per node is notO(1), butO(leaf descendants). Furthermore what woulddescendants of the treebe? Usuallydescendantsis a property of a node.O(2(...))is identical toO(...)and would usually written in this shorter way and2(N-Leaf)+Leafis just2N-Leaf.
– user10605163
Nov 16 '18 at 13:41
add a comment |
As you were told in another comment, the operation per node is notO(1), butO(leaf descendants). Furthermore what woulddescendants of the treebe? Usuallydescendantsis a property of a node.O(2(...))is identical toO(...)and would usually written in this shorter way and2(N-Leaf)+Leafis just2N-Leaf.
– user10605163
Nov 16 '18 at 13:41
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.– user10605163
Nov 16 '18 at 13:41
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.– user10605163
Nov 16 '18 at 13:41
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53331284%2ftime-complexity-of-a-tree-related-problem%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Isn't leaf descendants the number of all the nodes accessible from that leaf, so the descendants of
Rshould be 9?– JiaHao Xu
Nov 16 '18 at 4:30
1
9 descendants but 6 leaf descendants. So, a leaf is a node that does not have any children.
– billyb
Nov 16 '18 at 4:34
The link to the text is uncomfortable to read. Perhaps upload an image to a post
– JiaHao Xu
Nov 16 '18 at 4:35
Done! I couldn't do it by myself because I was lacking reputation, but nightfury1204 edited it for me, thanks!
– billyb
Nov 16 '18 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.
– Brady Dean
Nov 16 '18 at 4:36