I am often ill at ease with Landau (Big O) notation, because it seems often to b
ID: 662161 • Letter: I
Question
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)?O(g(n)) to mean that ultimately |f(n)|?k?|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)?
Explanation / Answer
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 Om(?).
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.