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)?