“Inserting a number in a sorted list will take O(N) time if there are ‘N’ numbers in the list.” is not true. Maintaining a sorted list has a O(logn) insertion cost by finding the index with binary search, equivalent to the given solution with a much simpler implementation. I understand this was likely chosen as an easy example for the two heaps pattern but think that could mislead some learners.
Hi Edgar Nelson, while it is true that in a sorted list, you can find the index with binary search in O(logn) complexity. There is still the matter of insertion. After inserting the number, the rest of the numbers in the list have to be shifted to keep the list sorted, which is why insertion in a sorted list takes O(N) time. If this was a binary search tree, then insertion would take O(logn) time. I hope this answers your question.
doh. Yup makes sense! Thanks 