Properties of asymptotic orders

Prerequirements:

In this post we’ll collect several properties of asymptotic orders which will be useful in the posts about number theory.

Meaning of equalities with asymptotic orders

Before seeing the properties of asymptotic orders, it’s worth clarifying some notations. In Definition A.3 we saw the meaning of asymptotic relationships of the kind

f = X(g) \tag{1}

with X \in \{O, o, \Theta\}.
We can note that, in this kind of notation, the asymptotic order symbol X appears just after the equality symbol, alone. Equation (1), technically speaking, is not an equality, but it’s just an asymptitic relationship: it’s a way for writing that “f is an X of g“.

Many times it’s convenient to adopt another type of notation, apparently similar to (1), where the asymptotic relationship symbol appears also on the left of the equality symbol, for example:

o(f) = O(f) \tag{2}

In this case, the asymptotic relationship symbol which appears on the left of the equality stands for any function having that asymptotic order. So (2) means:

\forall g = o(f): g = O(f) \tag{2'}

that is, all functions which are o(f) are also O(f) (by the way, this statement is true, as we’ll see in Property A.9, but now we are focusing just on notation).

We can note that the roles of asymptotic relationship symbols are very different depending on whether they appear on the right or on the left of the equality symbol:

  • Those ones which appear on the right of the equality symbol must be understanded according to Definition A.3;
  • Those ones which appear on the left of the equality symbol must be understanded as a function with that asymptotic order, with the universal quantifier (\forall).

So you have to not be misleaded by the presence of the equality symbol, which usually can be read indifferently from left to right or from right to left. For example, if we exchenge the terms of (2), we’ll obtain the following asymptotic relationship:

O(f) = o(f) \tag{3}

which, though, has a very different meaning with respect to (2). It means, in fact (compare with (2′)):

\forall g = O(f): g = o(f) \tag{3'}

that is, all functions which are O(f), according to the this relationships, would also be o(f), and this statement is generally false.

Sometimes asymptotic relationship symbols appear on the right of the equality symbol, but not alone. In this case they stand for some function with that asymptotic order; but this time not any function, but a fixed one. For example, the following formula:

2x^2 = x O(x) \tag{3}

means:

\exists f = O(x): 2x^2 = x f \tag{3'}

Still in the case when on the right there is not an asymptotic order alone, other asymptotic orders may appear of the left. In that case all asymptotic orders represent some functions, you have to use the universal quantificator for the leftside orders and the existential one for the rightside orders, placing the universal quantifiers before existential ones. For example, the following formula:

2x^2 O(1) = x O(x) \tag{4}

means:

\forall g = O(1) \exists f = O(x): 2x^2 g = x f \tag{4'}

Summarizing, we can formulate the following definition:

Equalities with asymptotic orders

If in an equality there are some asymptotic orders (O, o or \Theta), it must be understanded as follows:

  1. If on the right of the equality symbol there is an asymptotic order alone, the equality must be understanded according to Definition A.3, and any asymptotic order on the left must be understanded as a function with that asymptotic order, with the universal quantifier (\forall);
  2. If on the right of the equality symbol there is an asymptotic order and it’s not alone, but it’s part of an expression which optionally involves also other asymptotic orders, you must evaluate the following points in an orderly fashion:
    • All the asymptotic orders on the left of the equality symbol must be understanded as functions having those asymptotic orders, with the universal quantified (\forall)
    • All the asymptotic orders on the right of the equality symbol must be understanded as functions having those asymptotic orders, with the existential quantifier (\exists)

Let’s see some examples of the notation introduced with Definition A.8. Some of them match with the statements of some properties that we’ll see later in this post.

In the following table, we’ll assume f, g and h to be real functions, and a to be a real constant.

Formula Meaning Case of Definition A.8
-O(f) = O(f) \forall g = O(f): -g = O(f) 1
a \cdot O(f) = O(f) \forall g = O(f): a \cdot g = O(f) 1
O(f) g = O(fg) \forall h = O(f): hg = O(fg) 1
x + O(x) = O(x) \forall f = O(x): x + f = O(x) 1
2x = x + O(x) \exists f = O(x): 2x = x + f 2
x = O(x) + O(1) \exists f = O(x) \exists g = O(1): x = f + g 2
O(x) = O(x) + O(x) \forall f = O(x) \exists g = O(x) \exists h = O(x): f = g + h 2
O(x) + O(x) = O(x) \forall f = O(x) \forall g = O(x): f + g = O(x) 1

Properties with equalities

One function is a big Oh of its absolute value

Let f: I \rightarrow \mathbb{R}, where I is a upper unbounded subset of \mathbb{R}. Then:

f = O(|f|)

By Definition A.3, f is O(|f|) if there is a constant A \in \mathbb{R} such that definitively |f(x)| \leq A |f(x)|. But such a constant A exists, in fact the previous inequality is true (not only definitively, but always) by putting A := 1. So f = O(|f|).

One simple corollary of this property is that, if f assumes only non-negative values, then f = O(f): in fact in this case f = |f| and so, by Property A.4, f = O(|f|) = O(f). But there is also a stronger result. In fact, it’s not necessary for the function to be always non-negative, but it’s sufficient to be definitively non-negative:

A definitively non-negative function is a big Oh of itself

Let f: I \rightarrow \mathbb{R} a definitively non-negative function, where I is a upper unbounded subset of \mathbb{R}. Then:

f = O(f)

By Definition A.3, f is O(f) if there is a constant A \in \mathbb{R} such that definitively |f(x)| \leq A f(x). But f is definitively non-negative, so definitively we’ll have that |f(x)| = f(x), hence the condition |f(x)| \leq A f(x) is definitively satisfied with A := 1.

A function is O(1) if and only if it’s definitively bounded

Let f: I \rightarrow \mathbb{R}, where I is a upper unbounded subset of \mathbb{R}. Then:

f = O(1) \Leftrightarrow f \text{ is definitively bounded}

By Definition A.3, f is O(1) when there exists a constant A such that definitively |f(x)| \leq A, that is -A \leq f(x) \leq A. So f is a definitively bounded function.
Conversely, if f is definitively bounded, there exist two constants B and C such that definitively B \leq f(x) \leq C. Let’s consider a value of x which satisfies this inequality and let’s prove that -A \leq |f(x)| \leq A, with A := \max(|B|, |C|). First of all, let’s note that this choice of A implies that -A \leq B and C \leq A. In fact:

  • If B \geq 0, then -A = -\max(|B|, |C|) \leq 0 \leq B, so -A \leq B.
  • If B \lt 0, then \max(|B|, |C|) = \max(-B, |C|) \geq -B, so -A = -\max(|B|, |C|) = -\max(-B, |C|) \leq B, hence -A \leq B in this case too.
  • If C \lt 0, then C \leq 0 \leq \max(|B|, |C|) = A, so C \leq A.
  • If C \geq 0, then C = |C| \leq \max(|B|, |C|) = A, so C \leq A in this case too.

So we’ll have that -A \leq B \leq f(x) \leq C \leq A, hence -A \leq f(x) \leq A. Now we can distinguish between two cases:

  • If f(x) \geq 0, then f(x) = |f(x)|, so -A \leq f(x) \leq A \Rightarrow -A \leq |f(x)| \leq A.
  • If f(x) \lt 0, then f(x) = -|f(x)|, so -A \leq f(x) \leq A \Rightarrow -A \leq -|f(x)| \leq A. But, changing the sign to the latter inequality, we’ll have that A \geq |f(x)| \geq -A, that is again -A \leq f(x) \leq A.

Summarizing, all the xes which satisfy the relationship B \leq f(x) \leq C, satisfy also the relationship -A \leq |f(x)| \leq A. So, since the first relationship is definitively true, also the second one is definitively true, so f = O(1).

One example of a function which is O(1) is the function f(x) = \frac{1}{x}, defined on \mathbb{R}^{+}. In fact, for example, if x \geq 1 then |f(x)| \leq 1, so Definition A.3 is satisfied with A := 1. Then, by Property A.6, this function is definitively bounded, as you can see in the following picture. Note that, however, the function is unbounded: in fact it tends to infinity as x \to 0.

Figure 1: The function 1/x is O(1) and definitively limited

A simple consequence of Property A.6 is the case of constant functions. In fact, a constant function is obviously bounded (by itself), so it’s also definitively bounded, hence according to Property A.6 it’s O(1):

A constant function is O(1)

Let c: I \rightarrow \mathbb{R}, where I is an upper unbounded subset of \mathbb{R}, a constant function. Then:

c = O(1)

Normally, in the mathematical language, a constants c \in \mathbb{R} tends to be identified with a constant function with value c (defined on a not specified domain, usually all \mathbb{R}). So it may happen to find the definition of c \in \mathbb{R} first, and then to find an application of the relationship c = O(1): in this case, an homonym function c: \mathbb{R} \rightarrow \mathbb{R} is implicitly defined, such that c(x) = c for all x \in \mathbb{R}.

The product of two big Oh is a big Oh of the product

Let f, g: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definition A.8:

O(f) O(g) = O(fg)

Let h = O(f) and k = O(g); we have to prove that hk = O(fg). By definition, there exist two real constants A and B such that, definitively, |h(x)| \leq A f(x) and |k(x)| \leq B g(x). Then, still definitively, |h(x)| |k(x)| \leq A B f(x) g(x) \Leftrightarrow |(hk)(x)| \leq AB (fg)(x), where (hk) and (fg) are the product functions respectively of h by k and of f by g. Then, being AB a real constant, hk = O(fg).

Product of a big Of by a definitively non-negative function

Let f, g: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R} and g is definitively non-negative. Then, with the notation of Definition A.8:

O(f) g = O(fg)

By Property A.5, g = O(g). The thesis follows by applying Property A.7.

Product of a big Oh by a constant

Let f: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}; let c \in \mathbb{R}. Then, with the notation of Definition A.8:

O(f) c = O(f)

By Corollary 1 of Property A.6, c = O(1). The thesis follows by applying Property A.7.

A big Oh is invariant to sign change

Let f: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definition A.8:

- O(f) = O(f)

It’s enough to apply Corollary 2 of Property A.7, setting c := -1.

A big Oh does not change by summing up it to itself

Let f: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definition A.8:

O(f) + O(f) = O(f)

Let h = O(f) and k = O(f); we have to prove that h + k = O(f). By definition, there exist two real constants A and B such that, definitively, |h(x)| \leq A f(x) and |k(x)| \leq B f(x). Then, still definitively, |h(x)| + |k(x)| \leq (A + B) f(x). But |h(x) + k(x)| \leq |h(x)| + |k(x)|, so definitively |(h + k)(x)| = |h(x) + k(x)| \leq (A + B) f(x), where (h + k) is the sum function of h and k. Then, being A + B a real constant, h + k = O(f).

A small oh is also a big Oh

Let f, g: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definition A.8:

f = o(g) \Rightarrow f = O(g)

This property is an immediate consequence of Definition A.3. In fact, by this Definition, f = o(g) if, for any positive real constant A, definitively |f(x)| \leq A g(x), whereas f = O(g) if there exist a positive real constant A for which the same relationship is true. Clearly the first condition implies the second, so if f = o(g) then f = O(g).

Properties with inequalities

Sometimes asymptotic orders appear also within inequalities. In this cases we’ll adopt the following convention:

Inequalities with asymptotic orders

If inside an inequality there are some asymptotic orders (O, o or \Theta), they must be understanded as functions having those asymptotic orders, with the existential quantifier (\exists).

For example:

  • f \leq O(g) means \exists h = O(g) \text{ tale che } f \leq h
  • O(g) \leq f means \exists h = O(g) \text{ tale che } h \leq f

In addition we recall that, if we have two functions f and h defined on a set I, the notation f \leq h means that f(x) \leq h(x) for all x \in I.

In our posts about number theory, we’ll use the following properties of asymptotic orders with inequalities.

A function overestimated with absolute value by a big Oh is that big Oh

Let f, g: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definizions A.8 and A.9:

|f| \leq O(g) \Rightarrow f = O(g)

If |f| \leq O(g), it means that there is a function h = O(g) such that |f| \leq h. Being h = O(g), there is a positive real constant A such that definitively |h(x)| \leq A g(x). But, for all x, |f(x)| \leq h(x) \leq |h(x)|, so definitively also |f(x)| \leq A g(x), that is f = O(g).

A function that lays between two equal big Ohs is that big Oh

Let f, g: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definitions A.8 and A.9:

O(g) \leq f \leq O(g) \Rightarrow f = O(g)

If O(g) \leq f \leq O(g), it means that there are two functions h = O(g) and k = O(g) such that h \leq f \leq k. Since h = O(g), there is a positive real constant A such that definitively |h(x)| \leq A g(x). Analogously, there is a positive real constant B such that definitively |k(x)| \leq B g(x). Now let’s consider an x such that both these relationships are satisfied. Let’s distinguish two cases:

  • If f(x) \geq 0, then |f(x)| = f(x) \leq k(x) \leq |k(x)| \leq B g(x)
  • If f(x) \lt 0, then |f(x)| = -f(x) \leq -h(x) \leq |h(x)| \leq A g(x)

So, by setting C := \max(A, B), we’ll have that definitively |f(x)| \leq C g(x), that is f = O(g).

If a function is definitively overestimated by a big Oh, than it always is

Let f, g: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definitions A.8 and A.9:

f(x) \leq \left(O(g)\right)(x) \text{ definitivamente} \Rightarrow f \leq O(g)

If f(x) \leq \left(O(g)\right)(x) definitively, it means that there is a function h = O(g) such that f(x) \leq h(x) for all x \geq M, for some real constant M. We have to prove that f \leq O(g), i.e. that there is a function h^{\prime} = O(g) such that f(x) \leq h^{\prime}, for all x. Clearly when x \geq M we can take h^{\prime} = h, but we have to find a function that works with every x. For this purpose, let’s define the function h^{\prime} on I as follows:

h^{\prime}(x) := \begin{cases} f(x) & \text{ if $x \lt M$} \\ h(x) & \text{otherwise} \end{cases}

This function is O(g) because definitively (for x \geq M) coincides with h, which is O(g). At the same time, f(x) \leq h^{\prime} for all x; in fact:

  • If x \geq M, then h^{\prime}(x) = h(x) \geq f(x)
  • If x \lt M, then h^{\prime}(x) = f(x) \geq f(x)

So f \leq h^{\prime}, with h^{\prime} = O(g), hence f \leq O(g).

A function overestimated by a big Oh of another function in turn overestimated by a third function, is a big Oh of the latter

Let f, g, h: I \rightarrow \mathbb{R}, where I is a right unbounded subset of \mathbb{R}. Then, with the notation of Definitions A.8 and A.9:

f \leq O(g), g \leq h \Rightarrow f \leq O(h)

If f \leq O(g), it means that there is a function g^{\prime} = O(g) such that f \leq g^{\prime}. Being g^{\prime} = O(g), there is a real positive constant A such that definitively |g^{\prime}(x)| \leq A g(x). Then, for every x which satisfies this relationship, f(x) \leq g^{\prime}(x) \leq |g^{\prime}(x)| \leq A g(x) \leq A h(x). But, by Corollary 2 of Property A.7, A h = O(h), so definitively f(x) \leq \left( O(h) \right) (x). Then, by Property A.12, f \leq O(h).

Leave a Reply

Your email address will not be published.