When does Big-O notation apply to functions with arbitrary constants?

I am having trouble understanding if I can apply Big-O notation to the following circumstance. Suppose that $$Mxk_0=\sum_{j=1}^{M}xk_j, \hspace{0.5cm}\mbox{where 0 Regard all $$k_j$$ as being arbitrary in their collective interval. This leads me to believe that $$k_0<1$$ must be a constant. Now, let $$g(x)=xf(x)$$. We have $$\frac{g(x)}{k_0x}=\frac{1}{k_0}f(x).$$ Thus, $$\frac{1}{k_0}f(x)=O(f(x)).$$ Is this correct? I think it uses Big-O notation correctly, but I don't feel satisfied in justifying it because $$k_0$$ feels weirdly fickle.

• If $k_0$ is actually constant then yes, this is true.
– Ian
Feb 10, 2021 at 2:04

You might be worried that since $$k_0$$ can be arbitrarily close to $$0$$, the factor $$\frac1{k_0}$$ can be arbitrarily large. It's still valid to carry out $$O$$-notation reasoning treating $$\frac1{k_0}$$ as a constant, though. The point is that even if $$\frac1{k_0}$$ is really large, as long as we hold it constant, eventually $$x$$ will get big enough (or small enough, depending on which version of $$O$$ we're using) that it doesn't matter. One can formalize this argument and prove it from the definition of $$O$$-notation.
Still, it's often useful/informative to keep track of which parameters the constant factor hidden in the $$O$$ expression depends on. E.g. a paper might present its result as "$$g=O(f)$$, with a constant factor that does not depend on $$\epsilon$$", which is a stronger statement than just "$$g=O(f)$$".
• That was my worry, you are exactly right. This answer is helpful. Can you explain what is meant by "$g=O(f)$, with a constant factor that does not depend on $\epsilon$." What exactly is meant by $\epsilon$? Feb 10, 2021 at 3:52
• Oh, $\epsilon$ is just an arbitrary parameter that might appear in the definition of $g$ or $f$. Something like "For all $\epsilon>0$, there exists an algorithm $A_\epsilon$ that runs in $O(n^3)$ time (with a constant factor that does not depend on $\epsilon$) and outputs a solution whose score is at least $(1-\epsilon)c$, where $c$ is the optimal score."