# How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can be misleading.

I have an algorithm that is dependent on two parameters $n$ and $m$, which are the respective sizes of the two pieces of data it works on, like (for example) in the case of a substring search, where you have the size $n$ of the string being searched and the size $m$ of the pattern to be found.

I want to express that the algorithm is $O(n)$, but with a constant that is independent of the value of $m$.

A simple example is the recognition of a regular set, which is linear in the size of the input string, independently of the size of the regular expression defining the regular set, provided it has been compiled into a DFA (which is supposed to be amortized on many recognitions). This is usually implicit, but can I make it explicit when it is less obvious, or less well known.

The problem seems to be that people will often write $f(n)\in O(g(n))$ to mean that ultimately $|f(n)|\leq k\cdot |g(n)|$ even when $k$ actually depends on $m$. I realize that this depends on how you look at the problem, and whether you consider that the parameter of size $m$ is part of the data.

But then, how can one state unambiguously and clearly, but without being too verbose, that, though the size $m$ parameter is part of the data, the algorithm is $O(g(n))$ independently of $m$, i.e. the same constant $k$ can be used even though $m$ may grow arbitrarily? Is there a notation or terminology for it?

Is there a better way recommended by HABON (the High Authority on Big O Notation)?

• Useless comment: I really feel like starting a witch hunt for whoever used $=$ to mean $\in$. It's caused no ended of problems when trying to teach people. May 18 '15 at 12:20
• Too short for a real answer, but I'd happily write "$O(g(n))$, independent of $m$" or similar. May 18 '15 at 12:23
• What about $O(g(n)+0m)$? May 19 '15 at 7:48

The usual convention is to state upfront that your big O notations are with respect to $n$, and that whenever the constant depends on some parameter $m$, then you write $O_m(\cdot)$.
If in another paper you are fine with allowing the constant to also depend on the parameter $m$, then instead you state upfront that your big O notations are with respect to $n$, and the underlying constant could depend on $m$. Then you can use Luke Matheison's suggestions that if in some case your big O doesn't depend on $m$, then you mention that in that case the underlying constant doesn't depend on $m$; but that could be more confusing than the convention in the preceding paragraph.