I recently started studying the SVD and I was given the following
- Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix (2006) [PDF]
I can understand the main goal of the paper and how the algorithms are implemented but I have problem in understanding the calculation of $O (\cdot)$.For example, on page 9 it says that the algorithm needs $O(cm+c^2)$ additional space and $O(c^{2}m+c^{3})$ additional time.
It would be really helpful if someone could explain the calculation of $O (\cdot)$ in that algorithm in order to get used to calculate them on my own.