Time and space complexity of vector dot-product co

问题:

What is the time and space complexity of an algorithm, which calculates the dot product between two vectors with the length n?

回答1:

If the 2 vectors are a = [a1, a2, ... , an] and b = [b1, b2, ... , bn], then

The dot-product is given by a.b = a1 * b1 + a2 * b2 + ... + an * bn

To compute this, we must perform n multiplications and (n-1) additions. (I assume that this is the dot-product algorithm you are referring to).

Assuming that multiplication and addition are constant-time operations, the time-complexity is therefore O(n) + O(n) = O(n).

The only auxiliary space we require during the computation is to hold the 'partial dot-product so far' and the last product computed, i.e. ai * bi.

Assuming we can hold both values in constant-space, the space complexity is therefore O(1) + O(1) = O(1).