Compitino ASD 20/01/2016 / 3

Si definiscano formalmente le relazioni O, Ω, Θ, o, ω e si dimostri la verità o la falsità di ciascuna delle seguenti affermazioni, giustificando formalmente le risposte:

1. Se P(n) è un polinomio di grado k, allora P(n) = Θ(n^k)
2. n = O(n log log n)
3. n log log n = O(n^1+ε), per ogni ε > 0
4. f(n) = O(g(n)) se e solo se g(n) = Ω(f(n))
5. ω(f(n)) ∩ O(g(n)) = ∅

---

Definizioni

O(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) ≤ cf(n) ∀ n ≥ n₀}

O(f(n)) significa che esiste una funzione g(n) tale che, data una costante c maggiore di zero e un parametro zero n₀ maggiore o uguale a zero, g(n) è minore o uguale a f(n) per la costante per ogni n maggiore o uguale a n_0.

Ω(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) ≥ cf(n) ∀ n ≥ n₀}

Analogamente, o(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) < cf(n) ∀ n ≥ n₀} e ω(f(n)) = {g(n) : ∃ c > 0, n₀ ≥ 0, g(n) > cf(n) ∀ n ≥ n₀}

Θ(f(n)) = {g(n) : ∃ c₁ > 0, c₂ > 0, n₀ ≥ 0, c₁f(n) ≤ g(n) ≤ c₂f(n) ∀ n ≥ n₀}

ovvero, scelte due costanti diverse e maggiori di zero, per una costante vale O(f(n)) e per l'altra vale Ω(f(n)).

Se P(n) è un polinomio di grado k, allora P(n) = Θ(n^k)

Vero, poiché per la definizione di Θ, Θ(n^k) = {g(n) : ∃ c₁ > 0, c₂ > 0, n₀ ≥ 0, c₁f(n) ≤ g(n) ≤ c₂f(n) ∀ n ≥ n₀}.

Asintoticamente, i termini di grado inferiore a k si possono omettere, perché per ogni h < k, si ha che

$\underset{n\to \infty }{\lim }\frac{n^k}{n^h}=0$

Dunque, in un polinomio nella forma c_in^k+c_iin^k-1+c_iiin^k-2+ ... + c_in, basta considerare il termine di grado più alto (c_in^k) e prendere un c₁ < c_i e un c₂ > c_i

n = O(n log log n)

L'uguaglianza è vera se, per la definizione di O(n), n ≤ n log log n; dividendo entrambi i termini per n, si ottiene che 1 ≤ log log n, che è vero per tutti gli n ≥ e^2

n log log n = O(n^1+ε), per ogni ε > 0

n^1+ε si può scrivere anche n * n^ε, in questo modo è possibile dividere per n entrambi i membri. L'uguaglianza è verificata se log log n ≤ n^ε per ogni ε > 0.

L'uguaglianza si può dire verificata se è vero che:

$\underset{n\to \infty }{\lim }\frac{n^{\epsilon }}{loglogn}=0$

Ma applicando de l'hôpital, vediamo che

$\underset{n\to \infty }{\lim }\frac{\epsilon n^{\epsilon -1}}{\frac{1}{\mathrm{n}logn}}=\underset{n\to \infty }{\lim }\frac{\epsilon n^{\epsilon -1}*\mathrm{n}logn}{1}$

che tende a +∞.

La risposta alla domanda è quindi che non è possibile generalizzare l'equivalenza per ogni ε > 0.

f(n) = O(g(n)) se e solo se g(n) = Ω(f(n))

Vero, è la proprietà della simmetria trasposta.

ω(f(n)) ∩ O(g(n)) = ∅

Falso.

Per definizione (condizioni al contorno omesse), ω(f(n)) = {g(n) > cf(n)} e O(g(n)) = {f(n) ≤ cg(n)}, quindi g(n) > cf(n) ∩ f(n) ≤ cg(n) ⇒ f(n) < cg(n), che è esattamente ω(f(n)).