Time complexity of a tree related problem










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)






algorithm data-structures tree time-complexity







share|improve this question
























  • 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





    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















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)






algorithm data-structures tree time-complexity







share|improve this question
























  • 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





    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













2












2








2


0






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)






algorithm data-structures tree time-complexity







share|improve this question
















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)






algorithm data-structures tree time-complexity




algorithm data-structures tree time-complexity






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 16 '18 at 5:20







billyb

















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 of R should 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






  • 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












2 Answers
2






active

oldest

votes


















3














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.






share|improve this answer























  • 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 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


















-1














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.






share|improve this answer























  • 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











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
);



);













draft saved

draft discarded


















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









3














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.






share|improve this answer























  • 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 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















3














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.






share|improve this answer























  • 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 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













3












3








3







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.






share|improve this answer













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.







share|improve this answer












share|improve this answer



share|improve this answer










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 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

















  • 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 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
















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













-1














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.






share|improve this answer























  • 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
















-1














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.






share|improve this answer























  • 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














-1












-1








-1







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.






share|improve this answer













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.







share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 16 '18 at 4:54









JiaHao XuJiaHao Xu

687316




687316












  • 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

















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


















draft saved

draft discarded
















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Top Tejano songwriter Luis Silva dead of heart attack at 64

Image
Ramiro Burr's New Blog - to go back: www.ramiroburr.com From Latin rock to reggaeton, boleros to blues,Tex-Mex to Tejano, conjunto to corridos and beyond, Ramiro Burr has it covered. If you have a new CD release, a trivia question or are looking for tour info, post a message here or e-mail Ramiro directly at: musicreporter@gmail.com Top Tejano songwriter Luis Silva dead of heart attack at 64 By Ramiro Burr on October 23, 2008 8:40 AM | Permalink | Comments (12) | TrackBacks (0) UPDATE: Luis Silva Funeral Service details released Visitation 4-9 p.m. Saturday, Rosary service 6 p.m. Saturday at Porter Loring, 1101 McCullough Ave Funeral Service 10:30 a.m. Monday St. Anthony De Padua Catholic Church, Burial Service at Chapel Hills, 7735 Gibbs Sprawl Road. Porter Loring (210) 227-8221 Related New Flash: Irma Laura Lopez: long time record promoter killed in accident NewsFlash: 9:02 a.m. (New comments below) Luis Silva , one of the most well-known and prolif
Read more

政党

Image
政治主題的一部分 政党政治 政治光譜 左派 極左 中間偏左 中间派 中間偏左 激進中間 （ 英语 ： Radical centrism ） 中間偏右 右派 中間偏右 極右 政綱 極端 激进 （ 英语 ： Political radicalism ） 温和 （ 英语 ： Moderate ） 改良 混合 （ 英语 ： Syncretic politics ） 第三位置 保守 原教旨 反动 政党制度 无党制 （ 英语 ： Non-partisan democracy ） 一党制 一党优势制 兩黨制 多黨制 联盟 （ 英语 ： Coalition ） 懸峙國會 信任與支持 （ 英语 ： Confidence and supply ） 少數派政府 聯合政府 大聯合政府 聯合政府 National unity government （ 英语 ： National unity government ） Majority government （ 英语 ： Majority government ） 列表 各國執政黨 政治意識形態 政治主題頁 查 论 编 系列条目 政治 基本主题 各国政治 政治经济学 政治史 （ 英语 ： Political history ） 世界政治史 （ 英语 ： Political history of the world ） 政治哲学 政治体系 无政府主义 城邦 民主制 联盟制 （ 英语 ： Federacy ） 封建制 独裁制 委员会制 精英政治 君主制 议会制 总统制 半总统制 神权政治 学术门类 政治学 （政治学家） 国际关系学 （理论） 比较政治学 公共行政 官僚制 （基层） 灵活组织机构 （ 英语 ： Adhocracy ） 政策 公共政策 （ 原则 （ 英语 ： Public policy doctrine ） ） 公共利益 外交政策 政府机构 权力分立 立法机构 行政机构 司法机构 选举机构 相关主题 主权 政治行为理论 （ 英语 ： Theories of political behavior ） 政治心理学 生理与政治导向 （ 英语 ： Biology and political orientation ） 政治组织 （ 英语 ： Political organisation ） 下属系列 选举制度 选举（投票） 联邦主义 政府 意识
Read more

ReactJS Fetched API data displays live - need Data displayed static

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box; 0 I'm fetching data from API with axios which is live (counters, date and time etc.). When I display it, browser gets not responding because it gets a lot of requests. What I need just get a first snapshot of live data. Same goes for: var date = new Date; return (<p>date.toLacaleString()</p>) It gets live time (ticking every second) :D I just need date and time at that moment when it gets requested (snapshot). reactjs date time static axios share | improve this question edited Nov 16 '18 at 16:18 Sung M. Kim 17.9k 33 112 165 asked Nov 16 '18 at 13:39 Laurynas Žilinskas Laurynas Žilinskas 8 4 add a comment  |  0 I'm fetching data from API with axios which is live (counters, date and time etc.). When I display it, brow
Read more