0
$\begingroup$

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<k_j<1$.}$$ 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.

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

1 Answer 1

1
$\begingroup$

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)$".

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – lilliege
    Feb 10, 2021 at 3:52
  • $\begingroup$ 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." $\endgroup$
    – Karl
    Feb 10, 2021 at 6:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .