Merging K Sorted Linked Lists, Why is Complexity O(N * K * K), not O(N * K)
I have the following solution, but I'm hearing from other reviewers that it is O(N * K * K), not O(N * K) where N is the (max) length of the K lists and K is the number of lists. For example, given the lists [1, 2, 3] and [4, 5], N is 3 and K is 2.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private void advance(final ListNode listNodes, final int index) {
listNodes[index] = listNodes[index].next;
}
public ListNode mergeKLists(final ListNode listNodes) {
ListNode sortedListHead = null;
ListNode sortedListNode = null;
int associatedIndex;
do {
int minValue = Integer.MAX_VALUE;
associatedIndex = -1;
for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
final ListNode listNode = listNodes[listIndex];
if (listNode != null && listNode.val < minValue) {
minValue = listNode.val;
associatedIndex = listIndex;
}
}
if (associatedIndex != -1) {
if (sortedListNode == null) {
sortedListNode = new ListNode(minValue);
sortedListHead = sortedListNode;
}
else {
sortedListNode.next = new ListNode(minValue);
sortedListNode = sortedListNode.next;
}
advance(listNodes, associatedIndex);
}
}
while (associatedIndex != -1);
return sortedListHead;
}
}
My reasoning is that the body of the do-while loop will occur N times (as the do-while loop's stop condition is fulfilled when the longest list has been iterated through), while the do-while loop's for loop's body will occur K times (listNodes.length), yielding O(n * k).
Why is the above solution O(n * k * k) instead?
algorithm merge linked-list time-complexity big-o
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
add a comment |
I have the following solution, but I'm hearing from other reviewers that it is O(N * K * K), not O(N * K) where N is the (max) length of the K lists and K is the number of lists. For example, given the lists [1, 2, 3] and [4, 5], N is 3 and K is 2.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private void advance(final ListNode listNodes, final int index) {
listNodes[index] = listNodes[index].next;
}
public ListNode mergeKLists(final ListNode listNodes) {
ListNode sortedListHead = null;
ListNode sortedListNode = null;
int associatedIndex;
do {
int minValue = Integer.MAX_VALUE;
associatedIndex = -1;
for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
final ListNode listNode = listNodes[listIndex];
if (listNode != null && listNode.val < minValue) {
minValue = listNode.val;
associatedIndex = listIndex;
}
}
if (associatedIndex != -1) {
if (sortedListNode == null) {
sortedListNode = new ListNode(minValue);
sortedListHead = sortedListNode;
}
else {
sortedListNode.next = new ListNode(minValue);
sortedListNode = sortedListNode.next;
}
advance(listNodes, associatedIndex);
}
}
while (associatedIndex != -1);
return sortedListHead;
}
}
My reasoning is that the body of the do-while loop will occur N times (as the do-while loop's stop condition is fulfilled when the longest list has been iterated through), while the do-while loop's for loop's body will occur K times (listNodes.length), yielding O(n * k).
Why is the above solution O(n * k * k) instead?
algorithm merge linked-list time-complexity big-o
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
2
The outer loop is executed N * K times and the inner loop is executed K times
– Patrick Roberts
Nov 24 '18 at 2:21
@PatrickRoberts Why is the outer loop executed N * K times?
– TheeNinjaDev
Nov 24 '18 at 2:25
2
Your description of the condition for the outerwhileloop termination is incorrect. The actual condition is when all lists have been exhausted, which based on your definitions of N and K would be N * K iterations.
– Patrick Roberts
Nov 24 '18 at 2:27
@PatrickRoberts I see what you're saying now, I was only considering the longest list being exhausted rather than all of them. Thank you.
– TheeNinjaDev
Nov 24 '18 at 2:32
add a comment |
I have the following solution, but I'm hearing from other reviewers that it is O(N * K * K), not O(N * K) where N is the (max) length of the K lists and K is the number of lists. For example, given the lists [1, 2, 3] and [4, 5], N is 3 and K is 2.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private void advance(final ListNode listNodes, final int index) {
listNodes[index] = listNodes[index].next;
}
public ListNode mergeKLists(final ListNode listNodes) {
ListNode sortedListHead = null;
ListNode sortedListNode = null;
int associatedIndex;
do {
int minValue = Integer.MAX_VALUE;
associatedIndex = -1;
for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
final ListNode listNode = listNodes[listIndex];
if (listNode != null && listNode.val < minValue) {
minValue = listNode.val;
associatedIndex = listIndex;
}
}
if (associatedIndex != -1) {
if (sortedListNode == null) {
sortedListNode = new ListNode(minValue);
sortedListHead = sortedListNode;
}
else {
sortedListNode.next = new ListNode(minValue);
sortedListNode = sortedListNode.next;
}
advance(listNodes, associatedIndex);
}
}
while (associatedIndex != -1);
return sortedListHead;
}
}
My reasoning is that the body of the do-while loop will occur N times (as the do-while loop's stop condition is fulfilled when the longest list has been iterated through), while the do-while loop's for loop's body will occur K times (listNodes.length), yielding O(n * k).
Why is the above solution O(n * k * k) instead?
algorithm merge linked-list time-complexity big-o
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
I have the following solution, but I'm hearing from other reviewers that it is O(N * K * K), not O(N * K) where N is the (max) length of the K lists and K is the number of lists. For example, given the lists [1, 2, 3] and [4, 5], N is 3 and K is 2.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private void advance(final ListNode listNodes, final int index) {
listNodes[index] = listNodes[index].next;
}
public ListNode mergeKLists(final ListNode listNodes) {
ListNode sortedListHead = null;
ListNode sortedListNode = null;
int associatedIndex;
do {
int minValue = Integer.MAX_VALUE;
associatedIndex = -1;
for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
final ListNode listNode = listNodes[listIndex];
if (listNode != null && listNode.val < minValue) {
minValue = listNode.val;
associatedIndex = listIndex;
}
}
if (associatedIndex != -1) {
if (sortedListNode == null) {
sortedListNode = new ListNode(minValue);
sortedListHead = sortedListNode;
}
else {
sortedListNode.next = new ListNode(minValue);
sortedListNode = sortedListNode.next;
}
advance(listNodes, associatedIndex);
}
}
while (associatedIndex != -1);
return sortedListHead;
}
}
My reasoning is that the body of the do-while loop will occur N times (as the do-while loop's stop condition is fulfilled when the longest list has been iterated through), while the do-while loop's for loop's body will occur K times (listNodes.length), yielding O(n * k).
Why is the above solution O(n * k * k) instead?
algorithm merge linked-list time-complexity big-o
algorithm merge linked-list time-complexity big-o
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
asked Nov 24 '18 at 2:08
TheeNinjaDevTheeNinjaDev
2401313
2401313
2
The outer loop is executed N * K times and the inner loop is executed K times
– Patrick Roberts
Nov 24 '18 at 2:21
@PatrickRoberts Why is the outer loop executed N * K times?
– TheeNinjaDev
Nov 24 '18 at 2:25
2
Your description of the condition for the outerwhileloop termination is incorrect. The actual condition is when all lists have been exhausted, which based on your definitions of N and K would be N * K iterations.
– Patrick Roberts
Nov 24 '18 at 2:27
@PatrickRoberts I see what you're saying now, I was only considering the longest list being exhausted rather than all of them. Thank you.
– TheeNinjaDev
Nov 24 '18 at 2:32
add a comment |
2
The outer loop is executed N * K times and the inner loop is executed K times
– Patrick Roberts
Nov 24 '18 at 2:21
@PatrickRoberts Why is the outer loop executed N * K times?
– TheeNinjaDev
Nov 24 '18 at 2:25
2
Your description of the condition for the outerwhileloop termination is incorrect. The actual condition is when all lists have been exhausted, which based on your definitions of N and K would be N * K iterations.
– Patrick Roberts
Nov 24 '18 at 2:27
@PatrickRoberts I see what you're saying now, I was only considering the longest list being exhausted rather than all of them. Thank you.
– TheeNinjaDev
Nov 24 '18 at 2:32
2
2
The outer loop is executed N * K times and the inner loop is executed K times
– Patrick Roberts
Nov 24 '18 at 2:21
The outer loop is executed N * K times and the inner loop is executed K times
– Patrick Roberts
Nov 24 '18 at 2:21
@PatrickRoberts Why is the outer loop executed N * K times?
– TheeNinjaDev
Nov 24 '18 at 2:25
@PatrickRoberts Why is the outer loop executed N * K times?
– TheeNinjaDev
Nov 24 '18 at 2:25
2
2
Your description of the condition for the outer
while loop termination is incorrect. The actual condition is when all lists have been exhausted, which based on your definitions of N and K would be N * K iterations.– Patrick Roberts
Nov 24 '18 at 2:27
Your description of the condition for the outer
while loop termination is incorrect. The actual condition is when all lists have been exhausted, which based on your definitions of N and K would be N * K iterations.– Patrick Roberts
Nov 24 '18 at 2:27
@PatrickRoberts I see what you're saying now, I was only considering the longest list being exhausted rather than all of them. Thank you.
– TheeNinjaDev
Nov 24 '18 at 2:32
@PatrickRoberts I see what you're saying now, I was only considering the longest list being exhausted rather than all of them. Thank you.
– TheeNinjaDev
Nov 24 '18 at 2:32
add a comment |
1 Answer
1
active
oldest
votes
Your resulting list will have a maximum of n * k items. Adding each of those items costs O(k) (the inner loop performs k iterations to examine the head of each list). Therefore the total runtime is O(n * k * k).
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
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%2f53454615%2fmerging-k-sorted-linked-lists-why-is-complexity-on-k-k-not-on-k%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
Your resulting list will have a maximum of n * k items. Adding each of those items costs O(k) (the inner loop performs k iterations to examine the head of each list). Therefore the total runtime is O(n * k * k).
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
add a comment |
Your resulting list will have a maximum of n * k items. Adding each of those items costs O(k) (the inner loop performs k iterations to examine the head of each list). Therefore the total runtime is O(n * k * k).
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
add a comment |
Your resulting list will have a maximum of n * k items. Adding each of those items costs O(k) (the inner loop performs k iterations to examine the head of each list). Therefore the total runtime is O(n * k * k).
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
Your resulting list will have a maximum of n * k items. Adding each of those items costs O(k) (the inner loop performs k iterations to examine the head of each list). Therefore the total runtime is O(n * k * k).
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
edited Nov 24 '18 at 5:21
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
answered Nov 24 '18 at 2:25
jamesdlinjamesdlin
26.9k66193
26.9k66193
add a comment |
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%2f53454615%2fmerging-k-sorted-linked-lists-why-is-complexity-on-k-k-not-on-k%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
2
The outer loop is executed N * K times and the inner loop is executed K times
– Patrick Roberts
Nov 24 '18 at 2:21
@PatrickRoberts Why is the outer loop executed N * K times?
– TheeNinjaDev
Nov 24 '18 at 2:25
2
Your description of the condition for the outer
whileloop termination is incorrect. The actual condition is when all lists have been exhausted, which based on your definitions of N and K would be N * K iterations.– Patrick Roberts
Nov 24 '18 at 2:27
@PatrickRoberts I see what you're saying now, I was only considering the longest list being exhausted rather than all of them. Thank you.
– TheeNinjaDev
Nov 24 '18 at 2:32