I'm reading [1] where some columns and rows of a matrix $A$ are selected by their leverage scores aiming to have CUR decomposition of $A$. In the paper $c$ is a value determining how many indices we will select which is found as follows:
$c = O(k \log k / \epsilon^2)$
where $k$ stands for the number of right singular vectors selected and $\epsilon$ is an error value.
What I don't understand is that how can we assign a variable according to some big-O order of a value in the implementation of the algorithm. I can multiply $k \log k / \epsilon^2$ by any constant and it will behave asymptotically the same. But the results would be different in practice. More specifically, let me try to implement to see how it behaves, would I do something like
k = ...; eps = ...; c = round(k * log(k) / eps^2);
or should I do
scale = ...; # some constant like 2 c = round(scale * k * log(k) / eps^2);
How can I decide on the scale. What actually does this big-O order values for error bounds mean? Where should I look? Any recommendations are appreciated.
Mahoney, M. W., & Drineas, P. (2009). CUR matrix decompositions for improved data analysis. Proc. of the National Acad. of Sciences, 106(3), 697-702. doi:10.1073/pnas.0803205106