Mixing
Total number of paths between any two nodes - Graph vs. Complete Binary Tree
$begingroup$
In a graph, the total number of paths between any two nodes, is given by $n!$. Proof is in this link
In a Complete Binary tree, the total number of paths from root to leaf is basically, the number of leaves, which is $2^{log_2n - 1}$ and the time complexity of finding these is $O(n)$ since you would have to visit every node for doing so.
My question is, what is the time complexity of finding all paths between any two nodes in a complete binary tree ? Is it $2^n$ since from any node, you have two paths?
Cross posting from MathOverflow, as this is a more appropriate forum for the discussion in question.
graph-theory algorithms factorial computational-complexity trees
edited Jan 26 '18 at 0:29
bof
51.5k558120
asked Dec 3 '16 at 19:08
learningboylearningboy
285
$endgroup$
add a comment |
$begingroup$
In a graph, the total number of paths between any two nodes, is given by $n!$. Proof is in this link
In a Complete Binary tree, the total number of paths from root to leaf is basically, the number of leaves, which is $2^{log_2n - 1}$ and the time complexity of finding these is $O(n)$ since you would have to visit every node for doing so.
My question is, what is the time complexity of finding all paths between any two nodes in a complete binary tree ? Is it $2^n$ since from any node, you have two paths?
Cross posting from MathOverflow, as this is a more appropriate forum for the discussion in question.
graph-theory algorithms factorial computational-complexity trees
edited Jan 26 '18 at 0:29
bof
51.5k558120
asked Dec 3 '16 at 19:08
learningboylearningboy
285
$endgroup$
1
$begingroup$
I'm confused... in a tree, there is only ONE path between any two specified nodes.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:20
1
$begingroup$
And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:22
$begingroup$
@NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity.
$endgroup$
– learningboy
Dec 3 '16 at 19:29
add a comment |
$begingroup$
In a graph, the total number of paths between any two nodes, is given by $n!$. Proof is in this link
In a Complete Binary tree, the total number of paths from root to leaf is basically, the number of leaves, which is $2^{log_2n - 1}$ and the time complexity of finding these is $O(n)$ since you would have to visit every node for doing so.
My question is, what is the time complexity of finding all paths between any two nodes in a complete binary tree ? Is it $2^n$ since from any node, you have two paths?
Cross posting from MathOverflow, as this is a more appropriate forum for the discussion in question.
graph-theory algorithms factorial computational-complexity trees
edited Jan 26 '18 at 0:29
bof
51.5k558120
asked Dec 3 '16 at 19:08
learningboylearningboy
285
$endgroup$
In a graph, the total number of paths between any two nodes, is given by $n!$. Proof is in this link
In a Complete Binary tree, the total number of paths from root to leaf is basically, the number of leaves, which is $2^{log_2n - 1}$ and the time complexity of finding these is $O(n)$ since you would have to visit every node for doing so.
My question is, what is the time complexity of finding all paths between any two nodes in a complete binary tree ? Is it $2^n$ since from any node, you have two paths?
Cross posting from MathOverflow, as this is a more appropriate forum for the discussion in question.
graph-theory algorithms factorial computational-complexity trees
graph-theory algorithms factorial computational-complexity trees
edited Jan 26 '18 at 0:29
bof
51.5k558120
asked Dec 3 '16 at 19:08
learningboylearningboy
285
edited Jan 26 '18 at 0:29
bof
51.5k558120
asked Dec 3 '16 at 19:08
learningboylearningboy
285
edited Jan 26 '18 at 0:29
bof
51.5k558120
edited Jan 26 '18 at 0:29
bof
51.5k558120
edited Jan 26 '18 at 0:29
bof
51.5k558120
51.5k558120
asked Dec 3 '16 at 19:08
learningboylearningboy
285
asked Dec 3 '16 at 19:08
learningboylearningboy
285
asked Dec 3 '16 at 19:08
learningboylearningboy
285
285
1
$begingroup$
I'm confused... in a tree, there is only ONE path between any two specified nodes.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:20
1
$begingroup$
And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:22
$begingroup$
@NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity.
$endgroup$
– learningboy
Dec 3 '16 at 19:29
add a comment |
1
$begingroup$
I'm confused... in a tree, there is only ONE path between any two specified nodes.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:20
1
$begingroup$
And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:22
$begingroup$
@NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity.
$endgroup$
– learningboy
Dec 3 '16 at 19:29
1
1
$begingroup$
I'm confused... in a tree, there is only ONE path between any two specified nodes.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:20
$begingroup$
I'm confused... in a tree, there is only ONE path between any two specified nodes.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:20
1
1
$begingroup$
And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:22
$begingroup$
And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:22
$begingroup$
@NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity.
$endgroup$
– learningboy
Dec 3 '16 at 19:29
$begingroup$
@NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity.
$endgroup$
– learningboy
Dec 3 '16 at 19:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
From Wikipeida:
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.
I have no idea why you would want all paths between all nodes, but it would probably be bounded by at least $O(n^3)$, since you have $n(n-1)approx O(n^2)$ different nodes to choose from, and most depth-first search algorithms run in $O(n)$ time.
In short: $O(n)$ for finding the singular path between two nodes and $O(n^3)$ for finding all paths between any two nodes.
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f2042182%2ftotal-number-of-paths-between-any-two-nodes-graph-vs-complete-binary-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
From Wikipeida:
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.
I have no idea why you would want all paths between all nodes, but it would probably be bounded by at least $O(n^3)$, since you have $n(n-1)approx O(n^2)$ different nodes to choose from, and most depth-first search algorithms run in $O(n)$ time.
In short: $O(n)$ for finding the singular path between two nodes and $O(n^3)$ for finding all paths between any two nodes.
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
add a comment |
$begingroup$
From Wikipeida:
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.
I have no idea why you would want all paths between all nodes, but it would probably be bounded by at least $O(n^3)$, since you have $n(n-1)approx O(n^2)$ different nodes to choose from, and most depth-first search algorithms run in $O(n)$ time.
In short: $O(n)$ for finding the singular path between two nodes and $O(n^3)$ for finding all paths between any two nodes.
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
add a comment |
$begingroup$
From Wikipeida:
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.
I have no idea why you would want all paths between all nodes, but it would probably be bounded by at least $O(n^3)$, since you have $n(n-1)approx O(n^2)$ different nodes to choose from, and most depth-first search algorithms run in $O(n)$ time.
In short: $O(n)$ for finding the singular path between two nodes and $O(n^3)$ for finding all paths between any two nodes.
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
From Wikipeida:
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.
I have no idea why you would want all paths between all nodes, but it would probably be bounded by at least $O(n^3)$, since you have $n(n-1)approx O(n^2)$ different nodes to choose from, and most depth-first search algorithms run in $O(n)$ time.
In short: $O(n)$ for finding the singular path between two nodes and $O(n^3)$ for finding all paths between any two nodes.
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
answered Dec 3 '16 at 19:31
AlgorithmsXAlgorithmsX
4,1071828
4,1071828
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f2042182%2ftotal-number-of-paths-between-any-two-nodes-graph-vs-complete-binary-tree%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
1
$begingroup$
I'm confused... in a tree, there is only ONE path between any two specified nodes.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:20
1
$begingroup$
And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph.
$endgroup$
– Nick Peterson
Dec 3 '16 at 19:22
$begingroup$
@NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity.
$endgroup$
– learningboy
Dec 3 '16 at 19:29