# What does it mean to select $O(k \log k / \epsilon^2)$ indices?

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

-
As you said: the algorithm should behave the same with any constant, but in practice the specific value of the constant will matter. You should try evaluating imperically the performance of the algorithm for different values of the constant, and reach a conclusion on optimal values (that is, values that make the implementation either faster, or more numerically stable). – user2468 Dec 31 '11 at 0:34
I think I will go for this. – petrichor Jan 2 '12 at 11:29

The authors are apparently only interested in asymptotically bounding the value c. In algorithm theory (I assume this is computational linear algebra), the growth rate tends to matter more than absolute values, even if the differences you discuss may seem large. Here is the wiki entry on it

http://en.wikipedia.org/wiki/Big_O_notation

which also gives a precise definition. A good source is the standard text book in algorithms

The notation goes back to Knuth, if you'd like the source, in his famous

http://www.amazon.com/Art-Computer-Programming-Volumes-Boxed/dp/0201485419

Knuth usually discusses his concepts in great detail as well.

-
Actually, I know Big-O notation and asymptotic analysis well. But this is a different case. In algorithm analysis, we compute the complexity given the array has size N. For example we may have 2 additions in a loop, then the result will be 2 times the loop count. It is OK. Coefficient 2 is not leading here and we are not setting something to the complexity here. But in the question, I need to set some variable which is computed in Big-O notation. This is confusing part. – petrichor Jan 2 '12 at 11:35