Why is the time complexity of second solution O(m(n+m)).
1 Like
Since both lists are traversed in the solution, the time complexity is O(m(n+m)) where n and m are the lengths of the lists. We traverse both the list and merge the values in one of the list which makes the complexity O(m(n+m)).
Happy Learning.
Anum Hassan
Developer Advocate
Eduactive.io
Hi @Himanshu_Pandotra, I spent a lot of time thinking about this time complexity and I might be able to clarify @Anum_Hassan’s answer.
The O(n+m) part stems from having to possibly iterate over both lists in the while loop. The additional O(m) part stems from the insert / merge step, wherein you might have to traverse an m length list before making the insert. My initial confusion stemmed from thinking of the insert/ merge step as O(1).
@Anum_Hassan please correct me if this is totally off base / wrong! Haha thanks
7 Likes
Yes, you are right. The material should explicitly mention that O(m) is time complexity of element insertion. And, O(m+n) is for traversal.
And, this part is confusing too:
Both lists are not traversed separately so we cannot say that complexity is (m+n).
Both lists are traversed only once.
3 Likes
I hope your query has been resolved @Himanshu_Pandotra. Thank you @Lynn_S_Yu for pitching in the discussion. Thank you @Phuong_Pham for clarifying the concept.
I was confused and bothered not being able to find an answer, but “O(m) part stems from the insert / merge step” clears it up. Tysm seriously
In this case is “n” the initial size of the list being inserted into and “m” the size of the list that is not modified?
If I understand it correctly the number of times you’ll perform an insertion is the size of the unmodified list. And each insertion involves traversing the modified list whose size at any point is somewhere between its original size and the sum of both sizes. That would give you the number of insertions multiplied by (no more than) the sum of both sizes. That would mean the space complexity is indeed O(m) as the result only increments the space needed by the size of the unmodified list as opposed to Solution #1 where an additional list is created with all the elements from both giving us O(n+m) for space.
Does this sound right?
Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers