LOOP_CMPL: Answer


#1

IMO the answer should be O(N+M)time, O(N+M)space, since we consider the worst case. O(1)space shouldn’t be the correct option… Please correct me if I’m wrong.


#2

I too made this mistake but with further thinking I concluded that the answer is O(1) for space complexity. My reasoning is because all we are doing is rewriting the value for the ‘a’ and ‘b’ variables (i.e. we are not storing to a new variable for each iterative step of the ‘for’ loop).

If the question where a+i = a + rand(), then both space and time complexity would be O(N+M).
Hopefully this makes sense. Please correct me if I am mistaken!