This community-built FAQ covers the “Sort a Linked List” exercise from the lesson “Asymptotic Notation: Python”.
Paths and Courses
This exercise can be found in the following Codecademy content:
FAQs on the exercise Sort a Linked List
There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (
) below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
Agree with a comment or answer? Like (
) to up-vote the contribution!
Need broader help or resources? Head here.
Looking for motivation to keep learning? Join our wider discussions.
Learn more about how to use this guide.
Found a bug? Report it!
Have a question about your account or billing? Reach out to our customer support team!
None of the above? Find out where to ask other questions here!
Hi, is there any reason my code dosent accept as an answer:
def sort_linked_list(linked_list):
print(“\n---------------------------”)
print(“The original linked list is:\n{0}”.format(linked_list.stringify_list()))
new_linked_list = LinkedList()
lst =
s_lst = “”
node = linked_list.head_node
while linked_list:
if node == None:
s_lst = s_lst
break
lst.append(node.get_value())
lst = sorted(lst)
node = node.get_next_node()
for i in lst:
s_lst += str(i) + "\n"
new_linked_list = LinkedList(s_lst)
return new_linked_list
This is how I solved it. I probably could have done inserted the head node differently.
def sort_linked_list(linked_list):
print("\n---------------------------")
print(“The original linked list is:\n{0}”.format(linked_list.stringify_list()))
new_linked_list = LinkedList()
#Write Code Here!
while linked_list.head_node.next_node:
link = find_max(linked_list)
new_linked_list.insert_beginning(link)
linked_list.remove_node(link)
new_linked_list.insert_beginning(linked_list.head_node.value)
return new_linked_list
The exercise says that the runtime is N^2 because you run find_max, which has a runtime of N, N different times. But wouldn’t the runtime of find_max go down as you keep removing nodes from the linked list? Sure, the first time you run it it would be N, but then you remove the max that was found, so then it’s N-1 because there’s one fewer node to check, and then next time N-2, and so on and so forth, run N times. So wouldn’t it end up being less than N^2?
2 Likes
Couldn’t find the FAQ for the Asymptotic Notation Python quiz, so I’m posting it here.
In one question, the following function was said to be O(N^2) runtime:
def func_four(list):
for element in list:
print(list[0 : len(list)])
because “within the loop iteration we are making a copy of the list, which is a linear operation”. I assume that means the length of list affects runtime, as longer lists require more printing.
But in another question:
def func_three(list):
print(list)
for i in range(0, 100000):
print(i)
this had constant runtime, O(1). But doesn’t the length of list affect runtime here too, since making a copy of the list of variable length contributed a linear operation in the first question?
It should be N! Because we are decrementing the length of the linked list after every execution of loop
Hi @chip0021917487
I arrived at the same conclusion as you at first, that the runtime had to be less than N^2, for the reason you have stated
I briefly thought about @dondraper68 's conclusion as well, but decided the runtime cannot possibly be O(N!) simply because O(N!) is a longer runtime than O(N^2), and we know from @chip0021917487 's reasoning that the runtime must be LESS than O(N^2), not more
Why is the runtime O(N^2) then? Reasons:
- In the worst case scenario, we must run through the sort_linked_list loop N times given an input linked_list of size N, so its runtime is O(N)
- Still in the worst case scenario, in the first iteration through the sort_linked_list loop, we must run though the find_max loop N times as well given an input linked_list of size N, so its runtime is also O(N). Although it is true that in subsequent iterations N becomes smaller as we remove nodes from the linked_list, this effect becomes negligible as N approaches an infinite size (since infinity - 1 = infinity)
- Still in the worst case scenario, in the first iteration through the sort_linked_list loop, we must run though the remove_node loop N times as well given an input linked_list of size N, so its runtime is also O(N). Once again, although it is true that in subsequent iterations N becomes smaller as we remove nodes from the linked_list, this effect becomes negligible as N approaches an infinite size (since infinity - 1 = infinity)
Since the find_max loop and the remove_node loop are not nested (they are independent loops), we add their runtimes, so: runtime = O(N) + O(N). But as N approaches an infinite size, this simplifies to O(N) (since infinity + infinity = infinity)
Since the above loops’ runtime of O(N) is nested within the sort_linked_list loop, which is also O(N), we get a total runtime of O(N^2)
This reasoning is good enough for me to move on the next lesson. If you spot any errors in it and you think it is incorrect please let me know, I’ll be glad to learn a more correct line of reasoning
1 Like
Trying to wrap my head around the difference between these two statements if anyone can help. Specifically lines 19 and 20
