Costi di esecuzione / esercizio

Dimostrare che11

$\sqrt{n+10}=\Theta \left(\sqrt{n}\right)$

Dobbiamo dimostrare che esistono due valori c₁ e c₂ tali che vale

$c_1\sqrt{n}\le \sqrt{n+10}\le c_2\sqrt{n}$

Eleviamo tutto al quadrato per togliere le radici:

${c_1}^{2}n\le n+10\le {c_2}^{2}n$

Prima dimostriamo che esiste c₁

${c_1}^{2}n\le n+10\Rightarrow {c_1}^{2}n-n\le 10\Rightarrow n\left({c_1}^2-1\right)\le 10$

siccome n è sempre non negativo, ci basta verificare per quali valori di c₁² il termine dentro la parentesi è positivo. Quindi con c₁² ≥ 1 e n qualsiasi (es. 1) la disuguaglianza è verificata.

Poi dimostriamo che esiste c₂

$n+10\le {c_2}^{2}n\Rightarrow 10\le n\left({c_2}^2-1\right)$

In questo caso, la costante c₂² va calcolata in base a n

$\frac{10}{{c_2}^2-1}\le n$