[Java]

[alerulli166]

Salve a tutti, mi chiamo Alessandro e mi sono appena iscritto !!!!
Ho un esercizio da risolvere di informatica. In particolare sarebe un esercizio forse di analisi, ma è in ambito della complessità asintotica dei programmi java.
Il testo è questo:

dalla definizione di O(.), segue che una funzione $f(n)=O(g(n))$ se esistono due costanti positive c ed n0 tali che $f(n) \leq c*g(n)$
per ogni $n \geq n0$.

se $f(n) = n*\surd n $ e $g(n) = n^2$ dimostrare che $f(n) = O(g(n))$.
dovrebbe essere n radice n, ma non me lo scrive bene

Spero possiate aiutarmi grazie in anticipo a tutti.

[apatriarca]

Devi semplicemente applicare la definizione. Devi cioè mostrare che esistono quei due valori per cui quella disequazione è vera per tutti i valori che devi prendere in considerazione. Devi semplicemente osservare che \(\sqrt{n} \leq n\) per ogni \(n \geq 1\) da cui deriva ovviamente la corrispondente disequazione moltiplicando entrambi i lati della disequazione per \(n\).

[alerulli166]

Perfetto. Se invece $f(n)=n\surdn$ e $g(n)=n$, anche in questo caso, scegliendo $c=1$, $\surdn$ sarà semre maggiore $n$, per $n\geq1$. Questo per dimostrare che $f(n)=\Omega(g(n))$.

PS non capisco perchè la radice non me la fa.

Poi, se posso approfittare del tuo aiuto, come esercizio devo dimostrare che se $f(n)=O(g(n))$ e $g(n)=O(h(n))$, allora $f(n)=O(h(n))$. Cioè concettualmente, graficando le tre funzioni si vede che è cosi, ma in scrittura come lo dimostro???

Grazie mille.