Based on the last sentence of this lesson
However, the extra space used in solution#1 is reduced to O(m) in solution#2. Thus, it makes this a tradeoff between space and time.
I am trying to understand what this means, does this mean that solution#1 uses an O(m) space? And if that’s the case m should be the size of the list that is longer correct?
The sentence can be better visualized by first establishing what are the space complexities of the two lists. The lesson assumes as follows:
lst1 => O(n)
lst2 => O(m)
With the above assumption, the lesson states that both of the solutions already take O(m + n) space as both of the solutions take lst1 and lst2 as input. The sentence below talks about how much additional space the solution takes. This is the space not inclusive of the original O(m + n). To calculate that, let’s list down the total space used by the two solutions:
lst1 input size) + O(m) (lst2 input size)+ O(m + n) (new list to store elements from both lists which will eventually have the size as the sum of the two input lists lst1 and lst2)lst1 input size) + O(m) (lst2 input size)+ O(m) (As all elements are inserted from lst2 to lst1 which is equivalent to the size of lst2)With both of the solution space complexities above, we can deduce that the Solution 2 uses an additional space of only O(m) instead of what Solution 1 uses which is O(m+n). So, the extra space used in solution#1 is reduced to O(m) in solution#2.. Here m need not be the length of the lengthier list but just length of the second list which in this case is lst2.
Best Regards,
Team Educative
Thank you for the explanation!