Shouldnt the time-complexity for this problem be O(m+n) because there are two lists and there is a possibility that the two lists do not converge. In this case wouldnt it take O(m) time to compute length of L1 and O(n) time to compute length of L2 leading to O(m+n)?
Test for overlapping lists 7.4 (Java Edition)
We actually say n is the total number of nodes, which is the sum of the number of nodes from both lists.
1 Like
Denace
#3
But then, for the next solution where we are testing for overlapping lists among 2 lists which may have cycles, the time complexity has been mentioned as O(m + n). This is why I’m a bit confused.
Are you using O(n) and O(m+n) interchangeably?
0 Likes
I see what you mean here. It is still not a bug as we defined n accordingly in both paragraph as well. However, I understand your concern for confusion here, and it definitely shall have some change.
0 Likes
Denace
#5
Yes, i think it will remove confusion. Perhaps you can add something to the end of the book in future editions, where you mention things such as n = length of the longest input structure.
In any case, thanks for confirming promptly!
0 Likes