The worst case is not if every element has to be inserted at the last position in the target list, but at the last position reached when traversing the list in some way. If you happened to know that the elements are given in the correct order, you could maintain a pointer to the tail of the list, and keep inserting there, which would take $O(n)$. Note that even under this assumption, your reasoning is wrong, or at least imprecise. A simple way to forbid auxiliary data structures would be to require $O(1)$ memory overhead. Nothing in the problem statement forbids using auxiliary data structures. You made the assumption that there's no way to use an auxiliary data structure. It's somewhat poorly worded because it relies on precise reading, but fails to state some key assumptions, such as the fact that obtaining the elements to insert costs $O(n)$, comparing two elements can be done in $O(1)$, and the input domain is effectively unbounded (exercise: come up with an $O(n)$ algorithm if the inputs are integers in the range $$). The way it's worded, it's a bit of a trick question. This question is more about reading comprehension than about algorithms. This assumes that the insertion process creates the list nodes as it goes (as opposed to filling existing blank nodes). To insert each element, find the preceding element in the mapping, and insert the new element after this node. It's the sort of requirements that come up often in the real world of programming.Īnother solution with the same complexity would be to insert the elements into the target list as they come, and maintain a parallel data structure mapping element values to node pointers in the target list. (In such a scenario, you'd need to ensure that inserting one element is atomic.) So this question isn't just making strange requirements for the sake of being strange. This is allowed by the problem statement.Ī practical reason to do this, rather than insert the elements then sort, would be if the linked list object is shared with another thread that requires it to always be sorted. The proposed solution first does some preprocessing of the arguments to insert, then does the insertion proper. It doesn't say anything about any other data structure that you may choose to use. The question only says that the target list needs to be maintained in sorted order. However, the solution that I have says that we can first sort the elements in $O(n \log n)$ and then, we can insert them one by one in $O(n)$, giving us an overall complexity of $O(n \log n)$.įrom the given wording of the question, which solution is more apt? In my opinion, since the question mentions "linked list needs to be maintained in sorted order", I am inclined to say that we cannot sort the elements beforehand and then insert them in the sorted order. In my opinion, the answer should be $O(n^2)$ because in every insertion, we will have to insert the element in the right place and it is possible that every element has to be inserted at the last place, giving me a time complexity of $1 2 . What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order? Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |