Havel Hakimi complexity
Does anyone know what's the complexity of the Havel & Hakimi algorithm ?
If you sort at every step I'm thinking $n^2 log(n)$ but I'm not sure.
Please provide me with some resources / links or answer here. I was unable to find any. The only one I found was not free.
Thanks in advance !
graph-theory
asked Feb 20 '14 at 19:57
eagleking95
11
add a comment |
Does anyone know what's the complexity of the Havel & Hakimi algorithm ?
If you sort at every step I'm thinking $n^2 log(n)$ but I'm not sure.
Please provide me with some resources / links or answer here. I was unable to find any. The only one I found was not free.
Thanks in advance !
graph-theory
asked Feb 20 '14 at 19:57
eagleking95
11
add a comment |
Does anyone know what's the complexity of the Havel & Hakimi algorithm ?
If you sort at every step I'm thinking $n^2 log(n)$ but I'm not sure.
Please provide me with some resources / links or answer here. I was unable to find any. The only one I found was not free.
Thanks in advance !
graph-theory
asked Feb 20 '14 at 19:57
eagleking95
11
Does anyone know what's the complexity of the Havel & Hakimi algorithm ?
If you sort at every step I'm thinking $n^2 log(n)$ but I'm not sure.
Please provide me with some resources / links or answer here. I was unable to find any. The only one I found was not free.
Thanks in advance !
graph-theory
graph-theory
asked Feb 20 '14 at 19:57
eagleking95
11
asked Feb 20 '14 at 19:57
eagleking95
11
asked Feb 20 '14 at 19:57
eagleking95
11
asked Feb 20 '14 at 19:57
eagleking95
11
asked Feb 20 '14 at 19:57
eagleking95
11
11
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
You are right that using the usual sorting algorithm at every step will lead to a complexity of $O(n^2 log n)$. Say your sort takes $O(n log n)$, always.
Then you make $n$ of these sorts, leading to complexity $O(n^2 log n)$.
But for precision, since a degree is removed from the sequence at each iteration, there are $n - i + 1$ degrees left at the $i$-th iteration, so sorting is actually done in $O((n - i + 1) log (n -i + 1))$. In total, the algorithm ends up making $sum_{i = 1}^n i log(i)$ operations.
From Wolfram alpha, this sum is equal to $log(H(n))$, where $H(n) = Pi_{i = 1}^n i^i$ is the hyperfactorial. And from this question, I learned that this changes nothing and that the complexity of $log(H(n))$ is $O(n^2 log n)$.
And here's a free resource I could find where they claim, without explaining too much, that the algorithm can run in $O(n^2)$ if we sort cleverly.
But you should be able to figure it out. Say your sequence is already sorted in non-increasing order. Now, at the previous iteration, $k$ degrees of your sequence, call it $S$, got reduced by one. You shouldn't need to resort the whole thing. If something is misplaced, it can only be because $S[k] = S[k + 1]$ previously, and now $S[k] = S[k + 1] - 1$. So all you have to do is find the values $S[i..k]$ that are all equal, and swap them for the values $S[k + 1..j]$ that are all equal (I mean here, $i$ is the smallest index $leq k$ such that $S[i] = S[k]$ and of course, everything inbetween is equal to $S[k]$ since $S$ is sorted - similar for $j$ but in the other direction). You can make this swap in $O(n)$, hence a $O(n^2)$ algorithm.
edited Apr 13 '17 at 12:20
Community♦
1
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
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%2f683931%2fhavel-hakimi-complexity%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
You are right that using the usual sorting algorithm at every step will lead to a complexity of $O(n^2 log n)$. Say your sort takes $O(n log n)$, always.
Then you make $n$ of these sorts, leading to complexity $O(n^2 log n)$.
But for precision, since a degree is removed from the sequence at each iteration, there are $n - i + 1$ degrees left at the $i$-th iteration, so sorting is actually done in $O((n - i + 1) log (n -i + 1))$. In total, the algorithm ends up making $sum_{i = 1}^n i log(i)$ operations.
From Wolfram alpha, this sum is equal to $log(H(n))$, where $H(n) = Pi_{i = 1}^n i^i$ is the hyperfactorial. And from this question, I learned that this changes nothing and that the complexity of $log(H(n))$ is $O(n^2 log n)$.
And here's a free resource I could find where they claim, without explaining too much, that the algorithm can run in $O(n^2)$ if we sort cleverly.
But you should be able to figure it out. Say your sequence is already sorted in non-increasing order. Now, at the previous iteration, $k$ degrees of your sequence, call it $S$, got reduced by one. You shouldn't need to resort the whole thing. If something is misplaced, it can only be because $S[k] = S[k + 1]$ previously, and now $S[k] = S[k + 1] - 1$. So all you have to do is find the values $S[i..k]$ that are all equal, and swap them for the values $S[k + 1..j]$ that are all equal (I mean here, $i$ is the smallest index $leq k$ such that $S[i] = S[k]$ and of course, everything inbetween is equal to $S[k]$ since $S$ is sorted - similar for $j$ but in the other direction). You can make this swap in $O(n)$, hence a $O(n^2)$ algorithm.
edited Apr 13 '17 at 12:20
Community♦
1
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
add a comment |
You are right that using the usual sorting algorithm at every step will lead to a complexity of $O(n^2 log n)$. Say your sort takes $O(n log n)$, always.
Then you make $n$ of these sorts, leading to complexity $O(n^2 log n)$.
But for precision, since a degree is removed from the sequence at each iteration, there are $n - i + 1$ degrees left at the $i$-th iteration, so sorting is actually done in $O((n - i + 1) log (n -i + 1))$. In total, the algorithm ends up making $sum_{i = 1}^n i log(i)$ operations.
From Wolfram alpha, this sum is equal to $log(H(n))$, where $H(n) = Pi_{i = 1}^n i^i$ is the hyperfactorial. And from this question, I learned that this changes nothing and that the complexity of $log(H(n))$ is $O(n^2 log n)$.
And here's a free resource I could find where they claim, without explaining too much, that the algorithm can run in $O(n^2)$ if we sort cleverly.
But you should be able to figure it out. Say your sequence is already sorted in non-increasing order. Now, at the previous iteration, $k$ degrees of your sequence, call it $S$, got reduced by one. You shouldn't need to resort the whole thing. If something is misplaced, it can only be because $S[k] = S[k + 1]$ previously, and now $S[k] = S[k + 1] - 1$. So all you have to do is find the values $S[i..k]$ that are all equal, and swap them for the values $S[k + 1..j]$ that are all equal (I mean here, $i$ is the smallest index $leq k$ such that $S[i] = S[k]$ and of course, everything inbetween is equal to $S[k]$ since $S$ is sorted - similar for $j$ but in the other direction). You can make this swap in $O(n)$, hence a $O(n^2)$ algorithm.
edited Apr 13 '17 at 12:20
Community♦
1
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
add a comment |
You are right that using the usual sorting algorithm at every step will lead to a complexity of $O(n^2 log n)$. Say your sort takes $O(n log n)$, always.
Then you make $n$ of these sorts, leading to complexity $O(n^2 log n)$.
But for precision, since a degree is removed from the sequence at each iteration, there are $n - i + 1$ degrees left at the $i$-th iteration, so sorting is actually done in $O((n - i + 1) log (n -i + 1))$. In total, the algorithm ends up making $sum_{i = 1}^n i log(i)$ operations.
From Wolfram alpha, this sum is equal to $log(H(n))$, where $H(n) = Pi_{i = 1}^n i^i$ is the hyperfactorial. And from this question, I learned that this changes nothing and that the complexity of $log(H(n))$ is $O(n^2 log n)$.
And here's a free resource I could find where they claim, without explaining too much, that the algorithm can run in $O(n^2)$ if we sort cleverly.
But you should be able to figure it out. Say your sequence is already sorted in non-increasing order. Now, at the previous iteration, $k$ degrees of your sequence, call it $S$, got reduced by one. You shouldn't need to resort the whole thing. If something is misplaced, it can only be because $S[k] = S[k + 1]$ previously, and now $S[k] = S[k + 1] - 1$. So all you have to do is find the values $S[i..k]$ that are all equal, and swap them for the values $S[k + 1..j]$ that are all equal (I mean here, $i$ is the smallest index $leq k$ such that $S[i] = S[k]$ and of course, everything inbetween is equal to $S[k]$ since $S$ is sorted - similar for $j$ but in the other direction). You can make this swap in $O(n)$, hence a $O(n^2)$ algorithm.
edited Apr 13 '17 at 12:20
Community♦
1
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
You are right that using the usual sorting algorithm at every step will lead to a complexity of $O(n^2 log n)$. Say your sort takes $O(n log n)$, always.
Then you make $n$ of these sorts, leading to complexity $O(n^2 log n)$.
But for precision, since a degree is removed from the sequence at each iteration, there are $n - i + 1$ degrees left at the $i$-th iteration, so sorting is actually done in $O((n - i + 1) log (n -i + 1))$. In total, the algorithm ends up making $sum_{i = 1}^n i log(i)$ operations.
From Wolfram alpha, this sum is equal to $log(H(n))$, where $H(n) = Pi_{i = 1}^n i^i$ is the hyperfactorial. And from this question, I learned that this changes nothing and that the complexity of $log(H(n))$ is $O(n^2 log n)$.
And here's a free resource I could find where they claim, without explaining too much, that the algorithm can run in $O(n^2)$ if we sort cleverly.
But you should be able to figure it out. Say your sequence is already sorted in non-increasing order. Now, at the previous iteration, $k$ degrees of your sequence, call it $S$, got reduced by one. You shouldn't need to resort the whole thing. If something is misplaced, it can only be because $S[k] = S[k + 1]$ previously, and now $S[k] = S[k + 1] - 1$. So all you have to do is find the values $S[i..k]$ that are all equal, and swap them for the values $S[k + 1..j]$ that are all equal (I mean here, $i$ is the smallest index $leq k$ such that $S[i] = S[k]$ and of course, everything inbetween is equal to $S[k]$ since $S$ is sorted - similar for $j$ but in the other direction). You can make this swap in $O(n)$, hence a $O(n^2)$ algorithm.
edited Apr 13 '17 at 12:20
Community♦
1
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
answered Feb 22 '14 at 4:32
Manuel Lafond
2,592716
2,592716
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2fmath.stackexchange.com%2fquestions%2f683931%2fhavel-hakimi-complexity%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
