[Algoritmi] Dubbio su notazione Theta

[ZfreS]

Sto studiando algoritmi e strutture dati e studiando la notazione theta mi è sorto un dubbio riguardo ad un esempio proposto dal libro. Si vuole dimostrare formalmente che $1/2n^2-3n in Theta(n^2)$. Qusto lo capisco in quanto è il termine $n^2$ a prevalere nell'espressione, ma formalmente si dimostra così: bisogna determinare tre costanti positive $c_1$, $c_2$, $n_0$ in modo che $c_1n^2<=1/2n^2-3n<=c_2n^2$ dove $g(n)=n^2$. Dividendo per $n^2$ si ottiene $c_1<=1/2-3/n<=c_2$. A questo punto il libro dice: la disuguaglianza di destra può essere resa valida per qualsiasi valore di $n>=1$ scegliendo una costante $c_2>=1/2$. Analogamente la disuguaglianza di sinistra può essere resa valida per qualsiasi valore di $n>=7$ scegliendo $c_1<=1/14$.
Ciò che non ho capito è come ha trovato $c_1=1/14$, $c_2=1/2$ e $n_0=7$.
Potreste chiarirmi questo dubbio per favore?

[apatriarca]

I valori sono scelti in modo "arbitrario" a patto che le disuguaglianze siano vere. Di solito si fanno delle semplificazioni e memorizza il valore di \(n\) per cui tali semplificazioni sono possibili.

Per la disuguaglianza di destra ha semplicemente usato il fatto che \( - 3/n < 0 \) per ogni valore di \(n \ge 1.\) In questo intervallo di \(n\) hai quindi che \( 1/2 - 3/n < 1/2 \) e ha quindi scelto \(c_2\) uguale a questo valore.

Per l'altra disuguaglianza hai che
\[
\begin{align*}
c_1 &\leq \frac{1}{2} - \frac{3}{n} = \frac{n - 6}{2\,n}
\end{align*}
\]
A questo punto ha deciso di prendere \(n \ge 7\) in modo che \( \frac{n}{7} \leq n - 6\) e
\[ c_1 \leq \frac{n/7}{2\,n} = \frac{1}{14} \]

[ZfreS]

Ho capito, quindi, in generale, che procedura devo seguire per trovare dei valori appropriati? Bisogna scegliere il più piccolo valore intero come nel secondo caso per il $7$?

[apatriarca]

Non è necessario, prendi il numero che ti fa più comodo. Devi solo dimostrare che tali valori esistono, non trovare valori che siano in qualche modo 'minimi'..

[ZfreS]

Perfetto, adesso mi è chiaro. Ma per togliere ogni dubbio, mostro un altro esempio del libro: consideriamo una funzione quadratica $f(n)=an^2+bn+c$ generica, dove $a$, $b$, $c$ sono costanti e $a>0$. Escludendo i termini di ordine inferiore e ignorando la costante si ha $f(n) in Theta(n^2)$. Formalmente per dimostrare la stessa cosa, prendiamo le costanti $c_1=a/4$ e $c_2=7/4a$ e $n_0=2max(|b|/a, sqrt(|c|/a))$. In questo caso è stata data una dimostrazione formale, non sembra una scelta arbitraria come negli altri casi.

[vict85]

Ma è arbitraria, infatti risulta che \(f(n) = an^2 + o( n^2 )\) (per \(n\rightarrow \infty\)).

Supponiamo per comodità che tutti i coefficienti siano positivi. Allora ci si riduce ad avere \(f(n)\ge an^2\) per ogni \(n\). Fissato un qualche \(\delta > 0\), voglio trovare un \(N\) tale che \(f(n)\le (a + \delta)n^2\) per \(n > N\). Mi basta quindi trovare un \(N\) tale che \(-\delta n^2 + bn + c \le 0\) per \(n > N\).

Insomma, come il solito si hanno che le radici di quel polinomio sono \(\displaystyle N_{1,2} = \frac{- b \pm \sqrt{ b^2 - 4cd }}{2d} \). Dati i segni delle varie variabili che ho presupposto, basta porre \(\displaystyle N = \max \biggl(\frac{\sqrt{ b^2 + 4cd } - b}{2d},\;0\biggr) \).

[ZfreS]

Ottimo, posso dire di aver chiarito i miei dubbi. Grazie tante per i chiarimenti!