O grande
O grande
O grande in analisi, simbolo di rapporto limitato nell’intorno di un punto, introdotto, come l’analogo → o piccolo, da E. Landau per esprimere un confronto tra ordini di grandezza di funzioni. La lettera O è appunto l’iniziale di ordine. Non è richiesto che le funzioni considerate siano infinite o infinitesime, ma la nozione di O grande si applica in entrambi i casi, come in altri casi anche più generali. Si considerino in prima istanza funzioni aventi valore diverso da 0 in un intorno di un punto x0 (x0 escluso), dove può anche darsi il caso x0 = ∞. Si dice che ƒ è O grande di g, per x → x0, e si scrive ƒ(x) = O(g(x)) per x → x0, se in un intorno U di x0 il rapporto ƒ /g è limitato, cioè se esiste una costante k > 0 tale che |ƒ(x)/g(x)| ≤ k in U {x0}. Si noti che, nonostante la scrittura sia di tipo funzionale, O(g(x)) non rappresenta una funzione composta, ma solo un’espressione simbolica e l’uguaglianza ƒ(x) = O(g(x)) va intesa in “senso asimmetrico”, significando che il primo membro, che è una funzione ben definita, soddisfa una certa maggiorazione con la funzione g(x): non si scriverà pertanto O(g(x)) = ƒ(x).
La relazione di O grande è una relazione di ordine parziale non stretto (→ ordinamento) e segue delle regole particolari, che si ricavano dalla definizione, quali per esempio:
• se c è una costante non nulla, ƒ(x) = cO(g(x)) equivale a ƒ(x) = O(g(x));
• da ƒ(x) = h(x)O(g(x)) si deduce ƒ(x) = O(h(x)g(x)) e, più in generale, O(g(x))O(h(x)) = O(h(x)g(x));
• ƒ(x) = O(g(x)) e g(x) = O(h(x)) implica ƒ(x) = O(h(x)), cioè la relazione di O è transitiva;
• ƒ(x) = O(ƒ(x)), cioè la relazione di O è riflessiva;
• se ƒ(x) = O(g(x)) e g(x) = O(ƒ(x)) si dice che ƒ e g hanno ugual ordine di grandezza; tale circostanza viene talvolta indicata con il simbolo ≍;
• ƒ(x) = O(1) è sinonimo di ƒ(x) limitata (in un intorno di x0).
Per esempio, per x → +∞ risulta: x = O(x 2), lnx = O(x), x + sinx = O(x), x + 2x 3 = O(x 3), 1/x 2 = O(1/x), 2 + sinx = O(3 + cosx) e viceversa (3 + cosx) = O(2 + sinx), O(x 2) + O(x) = O(x 2). Per x → 0 risulta: x 2 = O(x), sin2x = O(x), lnx =O(1/x), ex = O(1). Se le funzioni non sono sempre diverse da zero, una maniera formale per definire la relazione di O grande è la seguente: ƒ(x) = O(g(x)) se esiste una funzione h(x) limitata in un intorno di x0 tale che ƒ(x) = g(x)h(x).
Un altro simbolo che si utilizza, soprattutto nei problemi di complessità, è Ω (omega grande): ƒ(x) = Ω(g(x)) equivale a g(x) = O(ƒ(x)), cioè esiste una costante M > 0 tale che ƒ(x) ≥ M ⋅ g(x).