13.1 Time Complexity of Compute the intersection of two sorted arrays

#1

First, I want to say thanks for writing this book, it is by far the best book I have read on the subject. I have a quick question on the final time complexity for 13.1 in the Python book. It is stated as O(m+n) where m and n are the lengths of the two input arrays. You aren’t however iterating through the lengths of both arrays – at worst, the loop breaks when it has fully gone through the larger of the two arrays. This seems like O(max(m,n)) or am I missing something?

0 Likes
#2

You’re mixing up the complexity of the loop - which is, you’re correct, O(max(m,n)) iterations - and the complexity of the program - which is O(m+n)

Also, it helps to put the title of the problem in the post title, because the problem numbers can vary between versions of the book. Thanks! :slight_smile:

0 Likes
#3

Thanks, I’ll fix the title. The book however uses the term “algorithmic complexity”. Isn’t the creation of the two arrays outside the bounds of the algorithm complexity? I.e. where is the additional complexity coming from?

0 Likes
#4

It’s not the creation of the two arrays that make the complexity O(m+n). It’s the access of potentially every entry in both arrays within the loop that gives it that complexity.

0 Likes
#5

Thanks, I see it now. The worst case is actually when the arrays are the same – the intersection is the whole list and we access each element of both arrays.

1 Like