How to get dot product of two sparsevectors in O(m+n) , where m and n are the number of elements in both vectors

Question

I have two sparse vectors X and Y and want to get the dot product in O(m+n) where m and n are the numbers of non-zero elements in X and Y. The only way I can think of is picking each element in vector X and traverse through vector Y to find if there is element with the same index. But that would take O(m * n). I am implementing the vector as a linked list and each node has an element.

Answer 1

You can do it if your vectors are stored as a linked list of tuples whith each tuple containing the index and the value of a non zero element and sorted by the index.

You iterate through both vectors, by selecting the next element from the vector where you are at the lower index. If the indexes are the same you multiply the elements and store the result.

Repeat until one list reaches the end.

Since you have one step per non zero element in each list, the complexity is O(m+n) as required.

Footnote: The datastructure doesn't have to be linked list, but must provide a O(1) way to access the next non 0 element and it's index.