In order to understand the difference in respect to the complexities (time and space), could someone compute both for the code without and with vectorization? I am not sure of the effect of the vectorization process and I would like to get it for a better understanding, if possible.
The big O notation is meant for asymptotic analysis of algorithmic complexity. If you are looking for the big O notation, both the vectorized and unvectorized form of np.dot(w, x) will be O(n) where n is the number of dimensions of x. Parallelization (in vectorization) has nothing to do with the sum total of the number of operations (n numbers should be multiplied and added); it only speeds up the run time by a constant factor.
Thank you, I got now that : it only speeds up the run time by a constant factor. But know :
Does it mean that Otime=Ospace=O(n) for both vectorized and unvectorized codes here ?
Parallelization is just a constant term in front of time complexity - please check this Stackoverflow post.
In theory vectorization of matrix/vector multiplication should achieve linear speedup (references: Wikipedia article on ‘Analysis of parallel algorithms’, Wikipedia article on ‘Speedup’). Space complexity should be O(n) without the constant term.
Thank you.