What is the meaning of $O(m+n)$?

Question

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. Is that right? I keep seeing this notation, especially when discussing graph algorithms. For example, you routinely see: $O(|V| + |E|)$ (e.g. see here).

Answer 1

You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables.

Simply speaking, since $$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$ you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent asymptotic upper bounds.

On the other hand $O(n+m)$ is different from $O(\min\{n,m\})$, since if you set $n=2^m$, you get $$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$$

Answer 2

Believe it or not, it seems (in my experience) that many algorithms people have actually not thought about what the big O notation formally means, and when asked about it, you can get several different answers. Some issues are discussed in the paper On Asymptotic Notation with Multiple Variables by Rodney R. Howell.

Curiously, it also seems that most introductory algorithms courses spend lots of time being very formal about big O notation with a single variable, and then the next weeks happily use the notation for graph algorithms with several variables in a casual way, without discussing what the notation actually means.

Answer 3

Part 1

I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've been taught, and what other misconceptions float around this topic. I wrote this in the form of an imaginary discussion.

The following discussion is based on the following papers:

• O-notation in algorithm analysis, Doctoral Thesis, Tampere University of Technology, volume 1427, October 2016. This is my doctoral thesis. Among other things, it shows that there is exactly one definition of O-notation suitable for algorithm analysis.
• Minimal characterization of O-notation in algorithm analysis, Theoretical Computer Science, Volume 713, pp. 31–41, February 2018. This is a follow-up to the thesis. It shows that the primitive properties provided in the thesis are not minimal, but if you remove locality, then they are.
• A general definition of O-notation for algorithm analysis, Bulletin of EATCS 117, October 2015. This is the first publication on the topic. It is subsumed by the thesis.

Notation

We will the use the following notation:

$$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}[1]{\mathcal{P}(#1)} \newcommand{\setb}[1]{\left\{#1\right\}} \newcommand{\land}{\text{ and }} \begin{aligned} & \text{Symbol} && \text{Meaning} && \text{Example} \\ & \text{ } && \text{ } && \text{ } \\ & \TN && \text{Natural numbers} && 0, 1, 2, 3, \dots \\ & \TR && \text{Real numbers} && -3, 0, 1.5, \pi, \dots \\ & X \to Y && \text{Functions from set X to set Y} && \TR \to \TR \\ & \subsets{X} && \text{Subsets of set X} && \subsets{\setb{0, 1}} = \setb{\emptyset, \setb{0}, \setb{1}, \setb{0, 1}} \\ & R_X && \text{Cost functions in set X} && X \to \TR^{\geq 0} \\ & f|A && \text{Restriction of function f to set A} \end{aligned} $$

Cost-functions

A cost-function in a set $X$ is an element of the set

$$ R_X = X \to \TR^{\geq 0}, $$

the set of all functions from $X$ to non-negative real numbers. Consider an algorithm whose input-set is $X$. The resource-consumption of that algorithm, for a given resource, is a function $f \in R_X$, where $f(x)$ returns the amount of resources the algorithm spends on input $x \in X$.

For example, a graph algorithm may take a graph over a set $V$ as an input. Then the input-set $X$ is the set of all graphs over $V$, and $f(x)$ is the amount of resources the algorithm spends on graph $x \in X$.

Shouldn't the parameter of a cost-function be an input-size?

No. Input-size does not make sense as a general concept. The mapping from the input-set is the most detailed characterization of the resourse-consumption of an algorithm.

How do you obtain cost-functions?

To obtain a cost-function of an algorithm, you specify the model of computation --- e.g. an abstract state machine together with its atomic instructions --- and assign the atomic instructions their cost-functions. These atomic cost-functions imply a cost-function for each algorithm as a sum of the cost-functions of the instructions that are executed for a given input.

By assigning the atomic cost-functions, you are making a decision on what to measure. You may first analyze a specific resource, and later change the atomic cost-functions when you want to measure something else. Note that 0 is also a valid cost for a given input.

How do you work with cost-functions?

Let $f, g \in R_X$, and $c \in \TR^{> 0}$. We will be writing things such as $g \leq c f$. But what does this mean?

If $\ominus : \TR^{\geq 0} \to \TR^{\geq 0}$ is a unary function, we lift it to $R_X$ by

$$(\ominus f)(x) = \ominus f(x).$$

If $\odot : \TR^{\geq 0} \times \TR^{\geq 0} \to \TR^{\geq 0}$ is a binary function, we lift it to $R_X$ by

$$(f \odot g)(x) = \odot(f(x), g(x)) = f(x) \odot g(x).$$

If $\mathord{\sim} \subset \TR^{\geq 0} \times \TR^{\geq 0}$ is a relation in $\TR^{\geq 0}$, we lift it to $R_X$ by

$$f \sim g \iff \forall x \in X: f(x) \sim g(x).$$

To summarize, operations on $\TR^{\geq 0}$ are lifted to $R_X$ elementwise. We then have

$$f \leq c g \iff \forall x \in X : f(x) \leq c g(x).$$

How do you work with sets of cost-functions?

Let $F, G \subset R_X$. We lift the operations on $\TR^{\geq 0}$ to $\subsets{R_X}$ by

$$ \begin{aligned} \ominus F & = \setb{\ominus f : f \in F}, \\ F \odot G & = \setb{f \odot g : f \in F \land g \in G}. \\ \end{aligned} $$

Algorithmic O-notation

The algorithmic O-notation is the proper class of functions

$$O = \setb{O_X : R_X \to \subsets{R_X} : X \text{ is a set}},$$

where

$$O_X(f) = \setb{g \in R_X : \exists c \in \TR^{> 0} : g \leq c f}.$$

For the expression inside the set-builder notation, we say that $g$ is linearly dominated by $f$, or $f$ linearly dominates $g$. Correspondingly, algorithmic O-notation is also called linear dominance.

There is a separate $O_X$ for each input-set $X$?

Yes. And all of these infinite number of set-specific O-notations must be consistent with each other. The O-notation is the proper class of those set-specific O-notations, not just one specific $O_X$ for a single set $X$. Also, the domain-set $X$ is important; remove it and you may end up in incorrect conclusions because of confusing your domain.

This is not what I've been taught?

The books and courses are currently using an incorrect formalization of algorithmic O-notation; give it some time.

What do you mean by incorrect formalization?

In the same way that iceskaters have a strong idea about what iceskating should look like, computer scientists have a strong idea about what algorithmic O-notation should look like.

Current formalizations of algorithmic O-notation in books and courses conflict with that idea.

Can you give a concrete example of this?

Let

$$\mathcal{F} = \setb{\setb{x \in \TN^2 : x \geq x_0} : x_0 \in \TN^2}$$

Introduction to Algorithms, 2nd. ed, page 50, formalizes O-notation in $\TN^2$ as:

$$ f \in O'_{\TN^2}(g) \iff \exists c \in \TR^{>0}, \exists A \in \mathcal{F}: f|A \leq c(g|A). $$

Let $f \in R_{\TN}$ be an arbitrary cost-function. Suppose $G : \TN^2 \to \TN$ is an algorithm with cost-function $g \in R_{\TN^2}$ such that $g(x, 0) = f(x)$, and $g(x, y) = 0$ when $y > 0$. Then $g \in O'_{\TN^2}(0)$; seems like a cheap algorithm to call. Create an algorithm $F: \TN \to \TN$ which computes $F(x) = G(x, 0)$ by calling $G$. Then $F$ has cost-function $f$. Hence, the O-set of $g$ does not tell you anything about how costly it is to call $G$.

How do you know that a formalization captures the idea of O-notation?

When the O-notation is formalized as linear dominance, you have a simple way to check whether a function is in an O-set. However, from this form it is hard to see whether it captures the right idea. Simply picking some version of local linear dominance as formalization is just guessing.

The solution is to approach formalization from a different viewpoint: simply write down the rules how you expect O-notation to work, and see what you get. A natural way to do this is to provide a set of equations which describe how O-notation preserves structure (see the cheat-sheet below).

After this is done, those equations are then up to discussion for the community: do they really capture the right idea? To facilitate this discussion, the equation-set is best made minimal, so that there are no redundant equations. For example, the cheat-sheet below is very redundant. However, they contain an equivalent minimal subset of 6 equations. Linear dominance falls out naturally from this equation-set. I'll come back to this.

Isn't some kind of asymptotic behavior essential to O-notation?

No. It is the scale-invariance ($c$) which in some cases allows to ignore a finite number of elements in the domain.

Isn't the O-notation used in mathematics defined differently?

Yes. There are multiple different concepts of O-notation, and each is used in a different context and different purpose. Most of them are a version of local linear dominance which we will come back to later. The O-notations most often seen in mathematics (e.g. series, approximation, convergence) localize to the neighorhoods of a single point, or to the neighborhoods of infinity. We concentrate on the algorithmic O-notation, which is used to analyze algorithms, and which does not use any localization. This is because in the context of algorithm analysis, every part of a cost-function is important!

Basic usage

Can I write $O_{\TN}(n^2)$?

Yes. It is clear what the implied function is.

Can I write $O(n^2)$?

No. It is not clear what the implied function is, because the domain is not known. For example, it could be any subset of integers, or even a subset of $\TN^2$. The domain matters.

Can I write $O_{\TN^2}(nm^2)$?

Yes, but with caution. In particular, you must first define an implicit ordering for the parameters; say an alphabetical order. Then $nm^2$ stands for $f \in R_{N^2}$ such that $f(m, n) = nm^2$, rather than $f(n, m) = nm^2$. These functions are different.

Can I write $O_{\TN^2}(n^2)$?

No. It is not clear whether $n$ refers to the first argument or the second argument. This case can be disambiguated by $O_{\TN^2}((m, n) \mapsto n^2)$.

Is $O_{\TN^2}((m, n) \mapsto n^2) = O_{\TN}(n^2)$?

No; the functions have different domains.

How do I use the O-notation?

Use the following cheat-sheet for the O-notation. It's like the rules for differentiation; you strive to develop a sufficiently large rule-set to avoid needing to use the definition directly ever again. Suppose $X$, $Y$, and $Z$ are sets, $\alpha, \beta \in \TR^{> 0}$, $f, g, u, v \in R_X$, $s : Y \to X$, and $C \subset \subsets{X}$ is a finite cover of $X$.

$$ \begin{aligned} & \text{Property} && \text{Definition} \\ & \text{ } && \text{ } \\ & \text{Order-consistency} && f \leq g \implies f \in O_X(g) \\ & \text{Reflexivity} && f \in O_X(f) \\ & \text{Transitivity} && (f \in O_X(g) \land g \in O_X(h)) \implies f \in O_X(h) \\ & \text{Orderness} && f \in O_X(g) \iff O_X(f) \subset O_X(g) \\ & \text{Zero-separation} && 1 \not\in O_{\TN^{>0}}(0) \\ & \text{One-separation} && n \not\in O_{\TN^{>0}}(1) \\ & \text{Zero-triviality} && O_X(0) = \setb{0} \\ & \text{Scale-invariance} && O_X(\alpha f) = O_X(f) \\ & \text{Bounded translation invariance} && O_X(f + \beta + \alpha) = O_X(f + \beta) \\ & \text{Power-homogeneity} && O_X(f)^{\alpha} = O_X(f^{\alpha}) \\ & \text{Additive consistency} && u O_X(f) + v O_X(f) = (u + v)O_X(f) \\ & \text{Multiplicative consistency} && O_X(f)^u O_X(f)^v = O_X(f)^{u + v} \\ & \text{Locality} && (\forall D \in C : (f|D) \in O_D(g|D)) \implies f \in O_X(g) \\ & \text{Scalar homogeneity} && \alpha O_X(f) = O_X(\alpha f) \\ & \text{Homogeneity} && u O_X(f) = O_X(u f) \\ & \text{Multiplicativity} && O_X(f) O_X(g) = O_X(fg) \\ & \text{Restrictability} && O_X(f)|D = O_D(f|D) \\ & \text{Additivity} && O_X(f) + O_X(g) = O_X(f + g) \\ & \text{Summation rule} && O_X(f + g) = O_X(\max(f, g)) \\ & \text{Maximum rule} && \max(O_X(f), O_X(g)) = O_X(\max(f, g)) \\ & \text{Maximum-sum rule} && \max(O_X(f), O_X(g)) = O_X(f) + O_X(g) \\ & \text{Sub-composability} && O_X(f) \circ s \subset O_Y(f \circ s) \\ & \text{Injective super-composability} && O_X(f) \circ s \supset O_Y(f \circ s) (s \text{ injective}) \end{aligned} $$

Shouldn't translation invariance hold also when $\beta = 0$?

No. Otherwise it would be possible for a cost-function $f \in R_X$ with $f(x) = 0$ for some $x \in X$ to be equivalent to another cost-function $f' \in R_X$ with $f'(x) \neq 0$. For example, we would have $O(1) = O(0)$ which are fundamentally different classes of cost-functions.

Why would this formalization be correct?

Perhaps because you can prove that the algorithmic O-notation is exactly the proper class of functions $\setb{O_X : R_X \to \subsets{R_X} : X \text{ is a set}}$ which satisfy the following properties:

• Order-consistency
• Transitivity
• One-separation
• Scale-invariance
• Sub-composability
• Sub-homogeneity (it's the same as homogeneity but with $\subset$ rather than $=$)

Questioning the validity of the formalization is equivalent to questioning the validity of these properties. Let's go over them.

The first two properties --- order-consistency and transitivity --- state that $f \in O_X(g)$ is a preorder relation which is consistent with pointwise comparison. One-separation says that not every function can be equivalent. Scale-invariance is the very reason you are defining the O-notation in the first place; acceleration by a constant is algorithmically boring. No-one probably objects to these; they are at the core of any formalization of O-notation in any context.

The last two --- sub-composability and sub-homogeneity --- are what makes this O-notation algorithmic. Sub-composability says that the O-notation preserves composition, which means that things still work even if you refactor a part of your algorithm to a sub-algorithm. Sub-homogeneity says that the O-notation preserves repetition, which means that things still work even if you repeat things in a loop.

Anything else to say about those properties?

There are no other formalizations of O-notation which satisfy the listed properties; algorithmic O-notation is uniquely defined. It can also be proved that the property-set above is minimal; for any of these properties, there exists an "O-notation" which breaks exactly that property and satisfies the others. Since the algorithmic O-notation satisfies these properties, they are not inconsistent either.

Any other ways to characterize linear dominance?

Linear dominance is the only formalization of O-notation which has the property that the following two modes of analysis always produce the same result:

• Carry out the cost-analysis exactly by performing a sequence of structure-preserving operations on cost-functions. Then compute the O-set of the final result. Matrix algorithms are often analyzed this way.
• Compute the O-sets of the atomic cost-functions, and carry out the cost-analysis of an algorithm purely in terms of O-sets, performing exactly the same operations to the O-sets as in the exact case. This is the usual way of analyzing algorithms.

Given any other formalization, it is possible to construct an instance of analysis where the two modes do not produce the same result.

Related notations

The related notations are

$$ \begin{aligned} o_X(f) & = \setb{g \in R_X : g \in O_X(f) \land f \not\in O_X(g)}, \\ \Omega_X(f) & = \setb{g \in R_X : f \in O_X(g) }, \\ \omega_X(f) & = \setb{g \in R_X : f \in O_X(g) \land g \not\in O_X(f)}, \\ \Theta_X(f) & = \setb{g \in R_X : g \in O_X(f) \land f \in O_X(g)}. \end{aligned} $$

Notice how the O-notation determines them all.

How do I use the related notations?

Convert back and forth between the O-notation and them using the above definitions, and derive analogous cheat-sheets for them. Left as an exercise!

Limit form

The notations can also be given in the following limit form. Let

$$ \begin{aligned} F & = \setb{x \in X : f(x) > 0}, \\ G & = \setb{x \in X : g(x) > 0}. \end{aligned} $$

Then

$$ \begin{aligned} f \in O_X(g) & \iff \sup \frac{f|F}{g|F} < \infty, \\ f \in o_X(g) & \iff \sup \frac{f|F}{g|F} < \infty \land \inf \frac{f|G}{g|G} = 0, \\ f \in \Omega_X(g) & \iff \inf \frac{f|G}{g|G} > 0, \\ f \in \omega_X(g) & \iff \inf \frac{f|G}{g|G} > 0 \land \sup \frac{f|F}{g|F} = \infty, \\ f \in \Theta_X(g) & \iff \sup \frac{f|F}{g|F} < \infty \land \inf \frac{f|G}{g|G} > 0. \end{aligned} $$

Here we use the convention that $x/0 = \infty$ for each $x \in \TR^{> 0}$. The restrictions are needed to avoid the case $0/0$.

Where is the limit in that?

I'll get back to this.

The definitions for $o$ and $\omega$ do not look familiar?

The formalizations of the $\omega$ and $o$-notations are also currently incorrect in books and courses; any other choice than the above is inconsistent with the O-notation.

This sufficient condition for $o$ might look more familiar:

$$ \begin{aligned} {} & \forall c \in \TR^{>0}: f \leq cg \\ \iff & \sup \frac{f|F}{g|F} = 0 \\ \implies & f \in o_X(g). \end{aligned} $$

Similarly for $\omega$:

$$ \begin{aligned} {} & \forall c \in \TR^{>0}: g \leq cf \\ \iff & \inf \frac{f|G}{g|G} = \infty \\ \implies & f \in \omega_X(g). \end{aligned} $$

Preorders

Let

$$f \preceq_X g \iff f \in O_X(g).$$

Then $\preceq_X$ is a preorder in $R_X$; i.e. a reflexive and transitive relation in $R_X$. A preorder generalizes a partial order in that there can be multiple elements equivalent to each other. The notations then become

$$O_X(f) = \setb{g \in R_X : g \preceq_X f },$$

$$o_X(f) = \setb{g \in R_X : g \prec_X f },$$

$$\Omega_X(f) = \setb{g \in R_X : g \succeq_X f },$$

$$\omega_X(f) = \setb{g \in R_X : g \succ_X f },$$

$$\Theta_X(f) = \setb{g \in R_X : g \approx_X f }.$$

That is, we may as well define the O-notation in a set $X$ as a preorder.

I've seen this analogue before!

Right, but it is not merely an analogue; it is an exact correspondence; an alternative view. It is possible to go back and reframe all of the discussion this far in terms of preorders, rather than O-notation. In terms of the preorders, $O_X(f)$ is a principal down-set of $\preceq_X$. Conversion of the cheat-sheet to preorder-form is left as an exercise.

Perhaps non-principal down-sets of $\preceq_X$ are relevant too?

That's right. I'll get back to this.

Worst/best/average case analysis

A grouping of set $X$ is a function $g : X \to Z$, where $Z$ is a set. For example, if your input-set $X$ is the set of all graphs over set $V$, you may take a function $g : X \to \TN^2$ which maps each graph $x \in X$ to a pair of integers $(n, m) \in \TN^2$, denoting the number of vertices and edges in that graph.

Why is it called a grouping?

The preimage $g^{-1}(\setb{z})$, where $z \in g(X)$, gives all the input-elements $x \in X$ which $g$ maps to the same property $z$; these preimages partition, or group, the input-set $X$. For the graph grouping example, $g^{-1}(\setb{(n, m)})$ gives all the graphs with $n$ vertices and $m$ edges.

Shouldn't a grouping be defined as surjective?

You could do that, but that definition would be harder to use (in my opinion). For example, in the graph grouping example, I could simply map to $\TN^2$, even if the graph-set does not contain graphs with all combinations of vertices and edges.

What is an extended cost-function?

An extended cost-function in a set $X$ is an element of $R^{\infty}_X = X \to (\TR^{\geq 0} \cup \setb{\infty})$.

What is worst-case analysis?

A worst-case analysis of $f \in R_X$ over a grouping $g : X \to Z$ is the study of $f^* \in R^{\infty}_{g(X)}$ such that $f^*(z) = \sup f(g^{-1}(\setb{z}))$, or some $O$-set which contains it.

What is a case?

A case over a grouping $g : X \to Z$ is a right-inverse of $g$. That is, a function $s : g(X) \to X$ such that $g \circ s = id_{g(X)}$.

What is a worst case?

A case $s : g(X) \to X$ over a grouping $g : X \to Z$ is called worst of $f \in R_X$, if

$$(f \circ s)(z) = \sup f(g^{-1}(\setb{z})).$$

A worst case may not exist. If it does though, then the worst-case analysis of $f$ over $g$ is essentially about studying the cost-function of an auxiliary algorithm which, given $(n, m)$, forwards the worst case $s(n, m)$ to the original algorithm.

For the graph grouping example, the worst case of $f$ over $g$ exists because the preimages (groups) are finite (assuming finite $V$).

What is best-case analysis and a best case?

The terms best-case analysis, and best case, are defined otherwise exactly as the worst case, but supremum is replaced with infimum, and $O$-set is replaced with $\Omega$-set.

What is average-case analysis?

Left as an exercise:p

Due to character count limitation, we'll continue in another answer...

Answer 4

Part 2

$$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}[1]{\mathcal{P}(#1)} \newcommand{\setb}[1]{\left\{#1\right\}} \newcommand{\land}{\text{ and }} $$

Algorithms

Are there cases where existing intuition on O-notation may not hold?

You may find that your existing intuition does not hold when the input-set is something else than a subset of $\TN^d$; say, a subset of $\TR^d$ instead. A cost-function can then be unbounded in a bounded set. However, if you keep modifying the O-notation in terms of the rules given in the cheat-sheet, you'll be fine.

Why would I use real numbers as inputs to my algorithms?

Hopefully because it is natural to your problem domain. Algorithms are not limited to those which a Turing machine can run. To truly understand what an algorithm is, you need to look at abstract state machines.

What do you mean "truly understand"?

I'll use an analogy.

Topology (continuous functions, limits, open sets, etc.) can be studied at various levels, starting from $\TR$, to $\TR^d$, to metric spaces and to topological spaces. At each level, the next level of abstraction subsumes the results from the previous level of abstraction without changing the flavor of the topic. The definition of a topological space is so simple that it is hard to imagine there being a more generalized structure for studying topology. Although I cannot claim that topological spaces encapsulate the "most abstract" version of topology, the more abstract and simpler the structure, the closer you are to truly understanding topology. That's because then you cannot rely on various other properties that happen to hold in your specific space.

Abstract state machines are to algorithms as topological spaces are to topology. Turing machines (and equivalents) encapsulate only a small subset of all algorithms.

Why would I be interested in algorithms which can never be implemented on actual computers?

Look at any book on computational geometry (which deals with problems such as finding a convex hull of points, or triangulation of a polygon). Those algorithms are defined in terms of real numbers (a large part of geometry can be said to study subsets of $\TR^d$). While real-world computers do not work with real numbers, it does not make these algorithms useless. They do encapsulate practical ideas. It is simply that, by the real number abstraction, you get to concentrate on what is essential, instead of getting bogged down to the details of floating point numbers. While it is an essential problem that the floating point numbers do not work like real numbers, that problem can now be dealt with separately.

Newton's method is also an algorithm under abstract state machines. And it takes as input a differentiable function, which is even more abstract than just real numbers. Want to approximate that algorithm in real-world computers stably using floating point numbers? Welcome to numerical mathematics.

The same thing can be said about matrix decompositions. Here too you want to separate the algorithm of, say, LU-decomposition, from how it can be implemented stably numerically.

Master theorems

Master theorems are a collection of theorems which provide a shortcut for computing the O-set (or related notation) of a cost-function of certain kinds of recursive algorithms.

Do Master theorems work for the algorithmic O-notation?

Yes. With the welcome change that you no longer need to care about "regularity" properties, which you may have seen. Things just work.

Master theorem over integers

Let $a \in \TR^{\geq 1}$, $b \in \TR^{\geq 2}$, $d \in \TR^{> 0}$, and $F \in R_{\TN^{\geq 1}}$. A Master function over integers is a function $T \in R_{\TN^{\geq 1}}$ defined by the recurrence equation

$$ T(n) = \begin{cases} a T(\lceil n/b \rceil) + F(n), & n \geq b, \\ d, & n < b. \end{cases} $$

The set of such functions is denoted by $M_I(a, b, d, F)$.

Theorem

Let $T \in M_I(a, b, d, F)$, and $F \in O_{\TN^{\geq 1}}(n^c)$, where $c \in R^{\geq 0}$. Then

$$ \begin{aligned} \log_b(a) < c & \implies T \in O_{\TN^{\geq 1}}(n^c), \\ \log_b(a) = c & \implies T \in O_{\TN^{\geq 1}}(n^c \log_b(bn)), \\ \log_b(a) > c & \implies T \in O_{\TN^{\geq 1}}(n^{\log_b(a)}). \end{aligned} $$

If $F \in \Theta_{\TN^{\geq 1}}(n^c)$, then each $O_{\TN^{\geq 1}}$ can be replaced with $\Theta_{\TN^{\geq 1}}$.

Master theorem over reals

Let $a \in \TR^{\geq 1}$, $b \in \TR^{> 1}$, $d \in \TR^{> 0}$, and $f \in R_{\TR^{\geq 1}}$. A Master function over reals is a function $t \in R_{\TR^{\geq 1}}$ defined by the recurrence equation

$$ t(x) = \begin{cases} a t(x / b) + f(x), & x \geq b, \\ d, & x < b. \end{cases} $$

The set of such functions is denoted by $M_R(a, b, d, f)$.

Theorem

Let $T \in M_R(a, b, d, f)$, and $f \in O_{\TR^{\geq 1}}(x^c)$, where $c \in \TR^{\geq 0}$. Then

$$ \begin{aligned} \log_b(a) < c & \implies t \in O_{\TR^{\geq 1}}(x^c), \\ \log_b(a) = c & \implies t \in O_{\TR^{\geq 1}}(x^c \log_b(bx)), \\ \log_b(a) > c & \implies t \in O_{\TR^{\geq 1}}(x^{\log_b(a)}). \end{aligned} $$

If $F \in \Theta_{\TR^{\geq 1}}(x^c)$, then each $O_{\TR^{\geq 1}}$ can be replaced with $\Theta_{\TR^{\geq 1}}$.

Local linear dominance

What is a filter basis?

A filter basis in a set $X$ is set of subsets $\mathcal{F} \subset \subsets{X}$ such that for each $A, B \in \mathcal{F}$ there exists $C \in \mathcal{F}$ such that $C \subset A \cap B$. A filter basis is the smallest amount of information you need to be able to make sense of limits, or more generally of limit inferior and limit superior. Let $f \in R_X$. Then

$$\limsup_{\mathcal{F}} f = \inf \setb{\sup f(A) : A \in \mathcal{F}},$$

$$\liminf_{\mathcal{F}} f = \sup \setb{\inf f(A) : A \in \mathcal{F}}.$$

Note that $\liminf$ and $\limsup$ always exist as numbers in $\TR^{\geq 0} \cup \setb{\infty}$, since $\inf$ and $\sup$ do by the completeness of $\TR^{\geq 0} \cup \setb{\infty}$. This is in contrast to the concept of a limit $\lim$, which is the number that is equal to both $\liminf$ and $\limsup$. Because of this conditional existence, limits are less useful for the current discussion.

What is local linear dominance?

Let $\mathcal{F}(X) \subset \subsets{X}$ be a filter basis for each set $X$. Suppose further that these filter bases are related by

$$\mathcal{F}(X') = \setb{F \cap X' : F \in \mathcal{F}}$$

for each $X' \subset X$. Then $\mathcal{F}$-local linear dominance is given by

$$O_X^{\mathcal{F}}(f) = \setb{g \in R_X : \exists c \in \TR^{> 0}, A \in \mathcal{F}(X) : (g|A) \leq c (f|A) }.$$

Local linear dominance has the same related notations as linear dominance, defined analogously.

How is linear dominance related to local linear dominance?

Linear dominance is $\mathcal{F}$-local linear dominance when $\mathcal{F}(X) = \setb{X}$ for each set $X$.

Limit forms

Local linear dominance can also be given in the following limit form. Let

$$ \begin{aligned} F & = \setb{x \in X : f(x) > 0}, \\ G & = \setb{x \in X : g(x) > 0}. \end{aligned} $$

Then

$$ \begin{aligned} f \in O^{\mathcal{F}}_X(g) & \iff \limsup_{\mathcal{F}(F)} \frac{f|F}{g|F} < \infty, \\ f \in o^{\mathcal{F}}_X(g) & \iff \limsup_{\mathcal{F}(F)} \frac{f|F}{g|F} < \infty \land \liminf_{\mathcal{F}(G)} \frac{f|G}{g|G} = 0, \\ f \in \Omega^{\mathcal{F}}_X(g) & \iff \liminf_{\mathcal{F}(G)} \frac{f|G}{g|G} > 0, \\ f \in \omega^{\mathcal{F}}_X(g) & \iff \liminf_{\mathcal{F}(G)} \frac{f|G}{g|G} > 0 \land \limsup_{\mathcal{F}(F)} \frac{f|F}{g|F} = \infty, \\ f \in \Theta^{\mathcal{F}}_X(g) & \iff \limsup_{\mathcal{F}(F)} \frac{f|F}{g|F} < \infty \land \liminf_{\mathcal{F}(G)} \frac{f|G}{g|G} > 0. \end{aligned} $$

For linear dominance, limit inferior and limit superior reduce to infimum and supremum, respectively. This explains the name of the limit form we used previously for linear dominance.

Definitions of $o$ and $\omega$ do not look familiar?

This sufficient condition for $o$ might look more familiar:

$$ \begin{aligned} {} & \forall c \in \TR^{>0}: \exists A \in \mathcal{F}(X): (f|A) \leq c(g|A) \\ \iff & \limsup_{\mathcal{F}(F)} \frac{f|F}{g|F} = 0 \\ \implies & f \in o^{\mathcal{F}}_X(g). \end{aligned} $$

Similarly for $\omega$:

$$ \begin{aligned} {} & \forall c \in \TR^{>0}: \exists A \in \mathcal{F}(X): (g|A) \leq c(f|A) \\ \iff & \liminf_{\mathcal{F}(G)} \frac{f|G}{g|G} = \infty \\ \implies & f \in \omega^{\mathcal{F}}_X(g). \end{aligned} $$

The $o^{\mathcal{F}}$ and $\omega^{\mathcal{F}}$ notations (in $X = \TN$) have been defined in books and courses this way, however, as definitions they are incorrect in the sense that they do not quite represent the strict versions of $O^{\mathcal{F}}$ and $\Omega^{\mathcal{F}}$.

Can I use local linear dominance to analyze algorithms?

No; simply because if I say anything else I'll be interpreted incorrectly. At any time during your analysis, you are to remain in the realms of the algorithmic $O$-notation.

After that disclaimer, a careful yes. Some versions of local linear dominance, under suitable conditions, imply linear dominance. In particular, this is the case when the cost-functions are positive and the filter-sets are cofinite. After checking that such conditions hold, you may use local linear dominance (e.g. limit forms) to deduce containment in linear dominance $O$-set. Note the difference in mind-set; local linear dominances are tools which you may or may not be able to apply in your specific case, and those tools are only meant to help you deduce containment of a function $g \in R_X$ in $O_X(f)$, not to be used in analysis themselves.

Can you give an example of that?

Particularly interesting for this discussion is the filter basis

$$\mathcal{F}(X) = \setb{X \setminus X^{< n} : n \in \TN},$$

whenever $X \subset \TN^d$ for some $d \in \TN$. In the thesis, I call the corresponding local linear dominance coasymptotic (although I'm not too happy about that name). The sets in these filter bases are cofinite. Especially the case $d = 1$ should look familiar; then $X \setminus X^{< n} = X^{\geq n}$.

Let $f \in R_{\TN^{>0}}$ be such that

$$f(n) = n^2 \lvert\sin(n)\rvert + n + 3.$$

Since $f > 0$, and

$$\limsup_{\mathcal{F}(\TN^{>0})} \frac{f(n)}{n^2} = 1 < \infty,$$

we have that $f \in O_{\TN^{>0}}^{\mathcal{F}}(n^2)$. Since the filter-sets are cofinite and $n^2 > 0$, we have that $f \in O_{\TN^{>0}}(n^2)$. The potential payoff here was that we got to compute the limit rather than finding a suitable $c \in \TR^{>0}$ for linear dominance. Here we used local linear dominance as a tool to deduce $f \in O_{\TN^{>0}}(n^2)$.

How would you have done that directly?

Perhaps like this:

$$n^2 \lvert\sin(n)\rvert + n + 3 \leq n^2 + n^2 + 3n^2 = 5n^2.$$

Well, not particularly hard either. Perhaps someone could find an example where finding $c$ is hard but computing the limit is easy?

Why did you study local linear dominance?

Three reasons.

First, in analogue to software development, they were my unit tests. If linear dominance really is the only suitable algorithmic O-notation, then any other candidate should fail in some way. I wanted to see exactly which properties each definition failed.

Second, as already discussed, they can sometimes by used as tool to deduce containment in an $O$-set.

Third, some of them are needed to show the minimality of the property-set I gave above.

Anything else about local linear dominance?

Local linear dominance can be generalized to cost-functions which are eventually non-negative, meaning $f : X \to \TR$ for which there exists $A \in \mathcal{F}(X)$ such that $f\|A \geq 0$. In the case of linear dominance, eventually non-negative functions are exactly the cost-functions (which are non-negative), so this generalization does not bring us anything new.

Multivariate notation

It seems we now also have a multivariate algorithmic O-notation?

If by multivariate you mean an algoritmic O-notation on the domain $\TN^d$, then yes, O-notation is also defined on that set, as it is in any set.

But I read a paper which proves that there cannot exist a multivariate algorithmic O-notation?

You are referring to

• On Asymptotic Notation with Multiple Variables, Rodney R. Howell, Technical Report 2007-4, 2008.

The content in that paper is fine, but its conclusion is incorrect. The abstract properties of O-notation given in that paper, together with scale-invariance, are in fact equivalent to asymptotic linear dominance (local linear dominance on $\TN^d$ where the filter-sets are of the form $x \geq n$). Hence, the paper only shows that asymptotic linear dominance is not suitable as an algorithmic O-notation, not that there cannot be any suitable definition of an algoritmic O-notation.

Algorithmic O-notation revisited

The O-notation is actually a bit more general than how I defined it at the beginning. Some people use expressions such as $2^{O_{\TN}(n)}$, and we need to resolve what that means.

How is the algorithmic O-notation really defined?

The algorithmic O-notation is the proper class of functions

$$O = \setb{O_X : P(R_X) \to \subsets{R_X} : X \text{ is a set}},$$

where

$$O_X(F) = \setb{g \in R_X : \exists f \in F, c \in \TR^{> 0} : g \leq c f}.$$

The difference is that, in all its generality, the set-specific O-notation $O_X$ takes in a set of functions $F \subset R_X$, and returns all functions $g \in R_X$ which are linearly dominated by at least one function $f \in F$. In the terminology of preorders, an O-set $O_X(F)$ is a down-set of the underlying preorder. In terms of the principal down-sets,

$$O_X(F) = \bigcup \setb{O_X(\setb{f}) : f \in F}.$$

If we introduce the abuse of notation $O_X(f) = O_X(\setb{f})$ for $f \in R_X$, then you'll see that before this section we studied an important special case of the O-notation.

So what does $2^{O_{\TN}(n)}$ mean?

Literally taken,

$$2^{O_{\TN}(n)} = \setb{2^f : f \in O_{\TN(n)}}.$$

However, when written in research papers, it is an abuse of notation for $O_{\TN}(2^{O_{\TN}(n)})$. The convention is: if there is an expression which contains O-notation, then the whole-thing is to be wrapped in O-notation. Similarly for the related notations.

To avoid ambiguity, I think it is be better to wrap these kinds of expressions inside explicit O-notations instead (or whatever notation is needed).

What does $\Omega_{\TN}(n)^{O_{\TN}(n)}$ mean?

Literally taken, the function-set

$$\setb{f^g : f \in \Omega_{\TN}(n) \land g \in O_{\TN}(n)}.$$

In contrast to the previous example, this time there is no reinterpretation as an O-set or $\Omega$-set based on convention, because the expression uses two different types of notations.

But $O_{\TN}(\Omega_{\TN}(n)^{O_{\TN}(n)})$ is unambiguous, right?

Yes.

Cheat-sheet revisited

Using our new understanding of O-notation, we are now able to prove new properties for our cheat-sheet:

$$ \begin{aligned} & \text{Property} && \text{Definition} \\ & \text{ } && \text{ } \\ & \text{Idempotence} && O(O(f)) = O(f), \\ & \text{Composability} && O(O(f) \circ s) = O(f \circ s). \end{aligned} $$

In addition, the cheat-sheet can be in the most part be generalized simply by replacing $f, g, h \in R_X$ with $F, G, H \subset R_X$, and $\in$ with $\subset$. Left as an exercise.