Help me! What is the time and space complexity of an algorithm, which calculates the dotproduct between to vectors with the length n. ?
+3
A:
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).
Ani
2010-09-19 01:06:14
Thank you. But I need to have it expresses with n. So the time complexity will be n+(n-1) and the space 2n?
Gæst
2010-09-19 01:15:24
The constants are not relevant to Big O - it's good enough to say that time complexity is `O(n)` and the space-complexity is `O(1)`. Or are you looking for Big Theta?
Ani
2010-09-19 01:25:22
@Ani: big-theta hides constants too (in this case, O = big-Theta). You mean perhaps an *equivalent*.
Alexandre C.
2010-09-19 01:53:13
@Alexandre C: I agree - In this case, I have provided Big Theta. Wasn't suggesting that (though reading my comment, that's what it sounds like), just whether the OP was aware that this was actually a tight bound.
Ani
2010-09-19 02:32:59