Proprietà degli ordini asintotici

Prerequisiti:

In questo articolo raccoglieremo varie proprietà degli ordini asintotici che ci saranno utili negli articoli di teoria dei numeri.

Significato delle uguaglianze con gli ordini asintotici

Prima di vedere le proprietà degli ordini asintotici, è bene chiarire alcune notazioni. Nella Definizione A.3 abbiamo visto il significato delle relazioni asintotiche del tipo

f = X(g) \tag{1}

con X \in \{O, o, \Theta\}.
Osserviamo che, in questo tipo di notazione, il simbolo di ordine asintotico X compare subito dopo il simbolo di uguaglianza, da solo. La (1), tecnicamente parlando, non è un’uguaglianza, ma è appunto una relazione asintotica: è un modo per scrivere che “f è un X di g“.

Molte volte risulta comodo un altro tipo di notazione, apparentemente simile alla (1), dove il simbolo di relazione asintotica compare anche a sinistra del simbolo di uguaglianza, ad esempio:

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

In questo caso, il simbolo di relazione asintotica che compare a sinistra dell’uguaglianza rappresenta una qualsiasi funzione che ha quell’ordine asintotico. Quindi la (2) significa:

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

cioè, tutte le funzioni che sono o(f) sono anche O(f) (a proposito, quest’affermazione è vera, come vedremo nella Proprietà A.10, ma per ora ci interessa solo la notazione).

Osserviamo che i ruoli dei simboli di relazione asintotica sono ben diversi a seconda se compaiono a destra o a sinistra del simbolo di uguaglianza:

  • Quelli che compaiono a destra del simbolo di uguaglianza, da soli, sono da interpretarsi secondo la Definizione A.3;
  • Quelli che compaiono a sinistra del simbolo di uguaglianza sono da interpretarsi come una funzione con quell’ordine asintotico, con il quantificatore universale (\forall).

Quindi non ci si deve far ingannare dalla presenza del simbolo di uguaglianza, che di solito può essere letto in entrambi i versi. Ad esempio, se scambiassimo di posto i termini della (2) otterremmo la seguente relazione asintotica:

O(f) = o(f)

che però ha un significato ben diverso dalla (2). Significa infatti (confrontare con la (2′)):

\forall g = O(f): g = o(f)

cioè tutte le funzioni che sono O(f), secondo la relazione indicata, sarebbero anche o(f), e quest’affermazione in generale è falsa.

Alcune volte i simboli di relazione asintotica compaiono a destra del simbolo di uguaglianza, ma non da soli. In questo caso rappresentano una certa funzione con quell’ordine asintotico; questa volta però non una funzione qualsiasi ma una funzione fissata. Ad esempio, la seguente formula:

2x^2 = x O(x)

significa:

\exists f = O(x): 2x^2 = x f

Sempre nel caso in cui a destra non compare un ordine asintotico da solo, a sinistra possono comparire altri ordini asintotici. In tal caso tutti gli ordini asintotici rappresentano delle funzioni, bisogna usare il quantificatore universale per gli ordini di sinistra e quello esistenziale per gli ordini di destra, mettendo i quantificatori universali prima di quelli esistenziali. Ad esempio, la seguente formula:

2x^2 O(1) = x O(x)

significa:

\forall g = O(1) \exists f = O(x): 2x^2 g = x f

Ricapitolando, possiamo formulare la seguente Definizione:

Uguaglianze con gli ordini asintotici

Se in un’uguaglianza compaiono degli ordini asintotici (O, o oppure \Theta), essa deve essere interpretata come segue:

  1. Se a destra del simbolo di uguaglianza compare un ordine asintotico da solo, l’uguaglianza deve essere interpretata secondo la Definizione A.3, e gli eventuali ordini asintotici presenti a sinistra devono essere interpretati come delle funzioni che hanno quell’ordine asintotico, col quantificatore universale (\forall);
  2. Se a destra del simbolo di uguaglianza compare un ordine asintotico e non è da solo, ma è parte di un’espressione che eventualmente coinvolge anche altri ordini asintotici, bisogna valutare nell’ordine i seguenti punti:
    • Tutti gli ordini asintotici a sinistra del simbolo di uguaglianza devono essere interpretati come delle funzioni che hanno quegli ordini asintotici, col quantificatore universale (\forall)
    • Tutti gli ordini asintotici a destra del simbolo di uguaglianza devono essere interpretati come delle funzioni che hanno quegli ordini asintotici, col quantificatore esistenziale (\exists)

Vediamo degli esempi della notazione introdotta con la Definizione A.8. Alcuni di essi corrispondono agli enunciati di alcune proprietà che vedremo successivamente in questo articolo.

Nella seguente tabella, si intende che f, g e h sono funzioni reali, mentre a è una costante reale.

Formula Significato Caso della Definizione 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

Proprietà con le uguaglianze

Una funzione è un O grande del proprio valore assoluto

Sia f: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora:

f = O(|f|)

Per la Definizione A.3, f è O(|f|) se esiste una costante A \in \mathbb{R} tale che definitivamente |f(x)| \leq A |f(x)|. Ma questa costante A esiste, infatti la precedente disuguaglianza è vera (non solo definitivamente, ma sempre) ponendo A := 1. Quindi f = O(|f|).

Un semplice corollario di questa Proprietà è che, se f assume solamente valori non negativi, allora f = O(f): infatti in questo caso f = |f| e quindi, applicando la Proprietà A.4, f = O(|f|) = O(f). Vale però anche un risultato più forte. Infatti, non è necessario che la funzione sia sempre non negativa, ma è sufficiente che lo sia definitivamente:

Una funzione definitivamente non negativa è un O grande di se stessa

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora:

f = O(f)

Per la Definizione A.3, f è O(f) se esiste una costante A \in \mathbb{R} tale che definitivamente |f(x)| \leq A f(x). Ma f è definitivamente positiva, quindi definitivamente si ha che |f(x)| = f(x), per cui la condizione |f(x)| \leq A f(x) è soddisfatta definitivamente con A := 1.

Restando sempre in tema di valore assoluto, vale anche la seguente Proprietà:

Il valore assoluto di un O grande è sempre un O grande

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

|O(f)| = O(f)

Dobbiamo dimostrare che, per ogni funzione g tale che g = O(f), |g| = O(f). Essendo g = O(f), per la Definizione A.3 esiste una costante A tale che definitivamente |g(x)| \leq A f(x). Ma ||g(x)|| = |g(x)| per ogni x, quindi anche ||g(x)|| \leq A f(x) definitivamente. Allora, sempre per la Definizione A.3, |g| = O(f).

Se una funzione è un O grande di un’altra, anche il suo valore assoluto lo è

Siano f: I \rightarrow \mathbb{R} una funzione e f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

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

Essendo f = O(g), |f| = |O(g)| (infatti, quest’ultima uguaglianza significa che esiste una funzione h = O(g) tale che |f| = |h|, ma per ipotesi possiamo porre h := f). Ma, per la Proprietà A.6, |O(g)| = O(g), quindi |f| = |O(g)| = O(g).

Una funzione è O(1) se e solo se è definitivamente limitata

Sia f: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora:

f = O(1) \Leftrightarrow f \text{ \`{e} definitivamente limitata}

Per la Definizione A.3, f è O(1) quando esiste una costante A tale che definitivamente |f(x)| \leq A, ossia -A \leq f(x) \leq A. Dunque f è una funzione definitivamente limitata.
Viceversa, se f è definitivamente limitata, esistono due costanti B e C tali che definitivamente B \leq f(x) \leq C. Consideriamo un valore di x che soddisfa questa disuguaglianza e dimostriamo che -A \leq |f(x)| \leq A, con A := \max(|B|, |C|). Per prima cosa, osserviamo che questa scelta di A garantisce che -A \leq B e C \leq A. Infatti:

  • Se B \geq 0, -A = -\max(|B|, |C|) \leq 0 \leq B, quindi -A \leq B.
  • Se B \lt 0, osserviamo che \max(|B|, |C|) = \max(-B, |C|) \geq -B, quindi -A = -\max(|B|, |C|) = -\max(-B, |C|) \leq B, per cui anche in questo caso -A \leq B.
  • Se C \lt 0, C \leq 0 \leq \max(|B|, |C|) = A, quindi C \leq A.
  • Se C \geq 0, C = |C| \leq \max(|B|, |C|) = A, per cui anche in questo caso C \leq A.

Quindi abbiamo che -A \leq B \leq f(x) \leq C \leq A, da cui -A \leq f(x) \leq A. A questo punto possiamo distinguere due casi:

  • Se f(x) \geq 0, allora f(x) = |f(x)|, quindi -A \leq f(x) \leq A \Rightarrow -A \leq |f(x)| \leq A.
  • Se f(x) \lt 0, allora f(x) = -|f(x)|, quindi -A \leq f(x) \leq A \Rightarrow -A \leq -|f(x)| \leq A. Ma, cambiando segno a quest’ultima disuguaglianza, abbiamo che A \geq |f(x)| \geq -A, ossia di nuovo -A \leq f(x) \leq A.

Ricapitolando, tutte le x che soddisfano la relazione B \leq f(x) \leq C, soddisfano anche la relazione -A \leq |f(x)| \leq A. Quindi, dato che la prima relazione è valida definitivamente, anche la seconda lo è, per cui f = O(1).

Un esempio di una funzione O(1) è la funzione f(x) = \frac{1}{x}, definita su \mathbb{R}^{+}. Infatti, ad esempio, per x \geq 1 si ha che |f(x)| \leq 1, quindi vale la Definizione A.3 con A := 1. Allora, per la Proprietà A.7, questa funzione è definitivamente limitata, come si vede nella figura seguente. Si noti che però, nonostante ciò, la funzione non è limitata: infatti tende a infinito per x \to 0.

Figura 1: la funzione 1/x è O(1) e definitivamente limitata

Una semplice conseguenza della Proprietà A.7 è il caso delle funzioni costanti. Infatti, una funzione costante è ovviamente limitata (da se stessa), quindi è anche definitivamente limitata, per cui in base alla Proprietà A.7 è O(1):

Una funzione costante è O(1)

Sia c: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente, una funzione costante. Allora:

c = O(1)

Normalmente, nel linguaggio matematico, si tende a identificare una costante c \in \mathbb{R} con una funzione costante di valore c (definita su un dominio non precisato, di solito su tutto \mathbb{R}). Quindi può capitare di trovare definita c \in \mathbb{R} e poi trovare applicata la relazione c = O(1): in questo caso, si sta implicitamente definendo una omonima funzione c: \mathbb{R} \rightarrow \mathbb{R}, tale che c(x) = c per ogni x \in \mathbb{R}.

Il prodotto di due O grande è un O grande del prodotto

Siano f, g: I \rightarrow \mathbb{R} due funzioni definitivamente positive, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

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

Siano h = O(f) e k = O(g); dobbiamo dimostrare che hk = O(fg). Per definizione, esistono due costanti reali A e B tali che, definitivamente, |h(x)| \leq A f(x) e |k(x)| \leq B g(x). Allora, sempre definitivamente, |h(x)| |k(x)| \leq A B f(x) g(x) \Leftrightarrow |(hk)(x)| \leq AB (fg)(x), dove (hk) e (fg) sono le funzioni prodotto rispettivamente di h per k e di f per g. Allora, essendo AB una costante reale, hk = O(fg).

Prodotto di O grande per una funzione definitivamente non negativa

Siano f, g: I \rightarrow \mathbb{R} due funzioni definitivamente positive, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente e g è definitivamente non negativa. Allora, con la notazione della Definizione A.8:

O(f) g = O(fg)

Per la Proprietà A.5, g = O(g). La tesi segue applicando la Proprietà A.8.

Prodotto di O grande per una costante

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente; sia c \in \mathbb{R}. Allora, con la notazione della Definizione A.8:

O(f) c = O(f)

Per il Corollario della Proprietà A.7, c = O(1). La tesi segue applicando la Proprietà A.8.

Un O grande è invariante rispetto al cambio si segno

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

- O(f) = O(f)

Basta applicare il Corollario 2 della Proprietà A.8, ponendo c := -1.

Nell’O grande di un prodotto di funzioni, si può portare fuori una funzione mai nulla

Siano f,g: I \rightarrow \mathbb{R} due funzioni definitivamente positive, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Sia f(x) \neq 0 per ogni x \in I. Allora, con la notazione della Definizione A.8:

O(fg) = f \cdot O(g)

Dobbiamo dimostrare che, se h = O(fg), allora esiste una funzione k = O(g) tale che h = fk.
Se h = O(fg), esiste una costante A tale che definitivamente |h(x)| \leq Af(x)g(x). Dividiamo questa relazione per |f(x)| (possiamo farlo perché per ipotesi f(x) \neq 0): |\frac{h(x)}{f(x)}| \leq A\frac{f(x)}{|f(x)|}g(x). La frazione \frac{f(x)}{|f(x)|} vale per ogni x o 1 o -1, quindi in particolare è minore o uguale di 1, per cui definitivamente |\frac{h(x)}{f(x)}| \leq A g(x). Questo significa che la funzione \frac{h}{f} è O(g). Inoltre, h = f \cdot \frac{h}{f}, dunque \frac{h}{f} è la funzione k che stavamo cercando.

Questa Proprietà è solo apparentemente molto simile al Corollario 1 della Proprietà A.8. Infatti, per la Definizione A.8, l’enunciato della Proprietà A.8A si traduce in:

\forall h = O(fg) \exists k = O(g): h = fk

Mentre l’enunciato del Corollario 1 della Proprietà A.8 si traduce in una formula molto diversa:

\forall h = O(f): hg = O(fg)

Un caso particolare della Proprietà A.8A si ha quando la funzione che si porta fuori è una funzione costante (o una costante):

Un O grande di una funzione per una costante non nulla è un O grande della funzione

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Sia c \in \mathbb{R}, c \gt 0. Allora, con la notazione della Definizione A.8:

O(cf) = O(f)

Per la Proprietà A.8A, O(cf) = c \cdot O(f) e, per il Corollario 2 della Proprietà A.8, c \cdot O(f) = O(f).

La somma di O grandi è un O grande della somma

Siano f, g: I \rightarrow \mathbb{R} due funzioni definitivamente positive, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

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

Dobbiamo dimostrare che, se k = O(f) e r = O(g), allora k + r = O(f + g). Essendo k = O(f), esiste una costante A tale che definitivamente |k(x)| \leq Af; analogamente, esiste una costante B tale che definitivamente |r(x)| \leq Bg. Allora definitivamente |(k + r)(x)| = |k(x) + r(x)| \leq |k(x)| + |r(x)| \leq Af(x) + Bg(x) \leq \max(A, B)f(x) + \max(A, B)g(x) = \max(A,B) \cdot (f(x) + g(x)). Quindi esiste una costante C := \max(A, B) tale che definitivamente |(k + r)(x)| \leq C(f(x) + g(x)), per cui k + r = O(f + g).

Un O grande non cambia sommandolo a se stesso

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

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

È interessante cominciare con una dimostrazione sbagliata. Possiamo osservare che O(f) + O(f) = 2 \cdot O(f), e quest’ultimo è O(f) per il Corollario 2 della Proprietà A.8. Ciò che è sbagliato è che il passaggio O(f) + O(f) = 2 \cdot O(f) assume che i due O(f) sulla sinistra siano la stessa funzione, ma quest’assunzione è falsa: possono essere funzioni diverse, ma entrambe O(f).
La dimostrazione corretta è che, per la Proprietà A.9, O(f) + O(f) = O(f + f) = O(2f); infine, per il Corollario della Proprietà A.8A, O(2f) = O(f).

La Proprietà A.9 può essere estesa a qualsiasi sommatoria finita di funzioni definitivamente positive f_1, \ldots, f_n, per ogni n \geq 1. Vale infatti la relazione:

\sum_{i=1}^n O(f_i) = O\left(\sum_{i=1}^n f_i\right)

La dimostrazione consiste semplicemente nell’applicare la Proprietà n - 1 volte.

Relazioni tra o piccolo e O grande

Un o piccolo è anche un O grande

Siano f, g: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente e g è definitivamente positiva. Allora, con la notazione della Definizione A.8:

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

Questa Proprietà è un’immediata conseguenza della Definizione A.3. Infatti, per questa Definizione, f = o(g) se, per ogni costante reale positiva A, definitivamente |f(x)| \leq A g(x), mentre f = O(g) se esite una costante reale positiva A per cui vale la stessa relazione. Chiaramente la prima condizione implica la seconda, quindi se f = o(g) allora f = O(g).

Un O grande di un O grande è sempre un O grande

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

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

Dobbiamo dimostrare che, se g = O(f) e h = O(g), allora h = O(f). Essendo g = O(f), per la Definizione A.3 esiste una costante A tale che definitivamente |g(x)| \leq A f(x). Analogamente, esiste una costante B tale che definitivamente |h(x)| \leq B g(x). Allora definitivamente |h(x)| \leq B g(x) \leq |B| |g(x)| \leq |B| A f(x), per cui esiste una costante C := |B| A tale che definitivamente |h(x)| \leq C f(x), ossia h = O(f).

Un O grande di un o piccolo è un o piccolo

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

O(o(f)) = o(f)

Dobbiamo dimostrare che, se g = o(f) e h = O(g), allora h = o(f). Quest’ultima relazione asintotica, per la Definizione A.3, significa che per ogni costante reale positiva A vale definitivamente la relazione |h(x)| \leq A f(x). Quindi, fissiamo una costante reale A \gt 0 e dimostriamo che |h(x)| \leq A f(x).
Sempre per la Definizione N.3, essendo h = O(g), esiste una costante reale positiva B tale che definitivamente |h(x)| \leq B g(x); inoltre, essendo g = o(f), per ogni costante reale positiva C vale definitivamente la relazione |g(x)| \leq C f(x). Allora, componendo le due disuguaglianze, abbiamo definitivamente che |h(x)| \leq B g(x) \leq B |g(x)| \leq BC f(x). Ma, visto che C può essere una qualsiasi costante, possiamo porre C := \frac{A}{B}, in modo da avere che |h(x)| \leq BC f(x) = B \frac{A}{B} f(x) = A f(x), come volevamo dimostrare.

Un o piccolo di un o piccolo è sempre un o piccolo

Sia f: I \rightarrow \mathbb{R} una funzione definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Allora, con la notazione della Definizione A.8:

o(o(f)) = o(f)

Dobbiamo dimostrare che, se g = o(f) e h = o(g), allora h = o(f). Quest’ultima relazione asintotica, per la Definizione A.3, significa che per ogni costante reale positiva A vale definitivamente la relazione |h(x)| \leq A f(x). Quindi, fissiamo una costante reale A \gt 0 e dimostriamo che |h(x)| \leq A f(x).
Sempre per la Definizione N.3, essendo h = o(g), per ogni costante reale positiva B vale definitivamente la relazione |h(x)| \leq B g(x); analogamente, essendo g = o(f), per ogni costante reale positiva C vale definitivamente la relazione |g(x)| \leq C f(x). Allora, componendo le due disuguaglianze, abbiamo definitivamente che |h(x)| \leq B g(x) \leq B |g(x)| \leq BC f(x). Ma, visto che B e C possono essere qualsiasi costanti, possiamo porre B := C := \sqrt{A} (dove \sqrt{A} è un numero reale positivo perché A \gt 0), in modo da avere che |h(x)| \leq BC f(x) = \sqrt{A} \sqrt{A} f(x) = A f(x), come volevamo dimostrare.

Proprietà con le disuguaglianze

A volte gli ordini asintotici compaiono anche all’interno di disuguaglianze. In questi casi si adotta la seguente convenzione:

Disguaglianze con gli ordini asintotici

Se in una disuguaglianza compaiono degli ordini asintotici (O, o oppure \Theta), essi devono essere interpretati come delle funzioni che hanno quegli ordini asintotici, col quantificatore esistenziale (\exists).

Ad esempio:

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

Ricordiamo inoltre che, se abbiamo due funzioni f e h definite su un insieme I, la notazione f \leq h significa che f(x) \leq h(x) per ogni x \in I.

Nei nostri articoli di teoria dei numeri utilizzaremo le seguenti proprietà degli ordini asintotici con le disuguaglianze.

Una funzione maggiorata in valore assoluto da un O grande è quell’O grande

Siano f, g: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente e g è definitivamente positiva. Allora, con le notazioni delle Definizioni A.8 e A.9:

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

Se |f| \leq O(g), vuol dire che esiste una funzione h = O(g) tale che |f| \leq h. Essendo h = O(g), esiste una costante reale positiva A tale che definitivamente |h(x)| \leq A g(x). Ma, per ogni x, |f(x)| \leq h(x) \leq |h(x)|, quindi definitivamente anche |f(x)| \leq A g(x), ossia f = O(g).

Una funzione compresa tra due O grande uguali è uguale a quell’O grande

Siano f, g: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente e g è definitivamente positiva. Allora, con le notazioni delle Definizioni A.8 e A.9:

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

Se O(g) \leq f \leq O(g), vuol dire che esistono due funzioni h = O(g) e k = O(g) tali che h \leq f \leq k. Essendo h = O(g), esiste una costante reale positiva A tale che definitivamente |h(x)| \leq A g(x). Analogamente, esiste una costante reale positiva B tale che definitivamente |k(x)| \leq B g(x). Consideriamo ora una x tale che valgano entrambe queste relazioni. Distinguiamo due casi:

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

Allora, ponendo C := \max(A, B), si ha che definitivamente |f(x)| \leq C g(x), ossia f = O(g).

Se una funzione è maggiorata da un O grande definitivamente, allora lo è sempre

Siano f, g: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente e g è definitivamente positiva. Allora, con le notazioni delle Definizioni A.8 e A.9:

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

Se f(x) \leq \left(O(g)\right)(x) definitivamente, vuol dire che esiste una funzione h = O(g) tale che f(x) \leq h(x) per ogni x \geq M, per qualche costante reale M. Dobbiamo dimostrare che f \leq O(g), cioè che esiste una funzione h^{\prime} = O(g) tale che f(x) \leq h^{\prime}, per ogni x. Chiaramente per x \geq M possiamo prendere h^{\prime} = h, ma dobbiamo trovare una funzione che vada bene per ogni x. Per fare ciò, definiamo la funzione h^{\prime} su I come segue:

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

Questa funzione è un O(g) perché definitivamente (per x \geq M) coincide con h, che è un O(g). Nel contempo, f(x) \leq h^{\prime} per ogni x; infatti:

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

Quindi f \leq h^{\prime}, con h^{\prime} = O(g), per cui f \leq O(g).

Una funzione maggiorata da un O grande di un’altra funzione a sua volta maggiorata da una terza, è un O grande di quest’ultima

Siano f, g, h: I \rightarrow \mathbb{R}, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente e sia g che h sono definitivamente positive. Allora, con le notazioni delle Definizioni A.8 e A.9:

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

Se f \leq O(g), vuol dire che esiste una funzione g^{\prime} = O(g) tale che f \leq g^{\prime}. Essendo g^{\prime} = O(g), esiste una costante reale positiva A tale che definitivamente |g^{\prime}(x)| \leq A g(x). Allora, per ogni x che soddisfa questa relazione, f(x) \leq g^{\prime}(x) \leq |g^{\prime}(x)| \leq A g(x) \leq A h(x). Ma, per il Corollario 2 della Proprietà A.8, A h = O(h), quindi definitivamente f(x) \leq \left( O(h) \right) (x). Allora, per la Proprietà A.14, f \leq O(h).

Una proprietà con l’integrale

Nella seguente Proprietà, diversamente dalle precedenti, quando adotteremo la notazione O(f) per indicare una funzione reale g = O(f), supporremo non solo che g sia definita su un sottoinsieme illimitato superiormente di \mathbb{R}, ma in aggiunta supporremo che il suo insieme di definizione sia un intervallo del tipo [a, +\infty), con a \in \mathbb{R}, e che g sia integrabile in ogni intervallo del tipo [a, b], con b \in \mathbb{R}. Ci occorrono queste ipotesi aggiuntive perché la funzione O(f) comparirà in una funzione integrale del tipo \int_a^x O(f) dt. Infatti, affinché questa funzione sia ben definita, la funzione integranda deve essere definita nell’intervallo [a, +\infty) e integrabile in ogni sua porzione finita del tipo [a, b]. Ometteremo la dimostrazione, che sarebbe molto tecnica e più lunga di quelle viste in precedenza.

La funzione integrale di un O grande è un O grande dell’integrale della funzione

Sia f: I \rightarrow \mathbb{R} una funzione reale definitivamente positiva, dove I è un sottoinsieme di \mathbb{R} illimitato superiormente. Sia a \in \mathbb{R}. Allora, con le notazioni della Definizione A.8:

\int_a^x O(f) dt = O(\int_a^x f dt)

dove la x è la variabile della funzione integrale, e O(f) rappresenta una funzione g: [a, +\infty) \rightarrow \mathbb{R} integrabile in ogni intervallo del tipo [a, b], con b \in \mathbb{R}.

Quest’ultima Proprietà continua a valere se al posto di O grande si considera il simbolo o piccolo; tuttavia per brevità non enunciamo una nuova proprietà con questa modifica.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.