Dubbi su analisi asintotica
salve a tutti, potreste spiegarmi come muovermi per risolvere questi esercizi?:
(a) Provare che $5n \sqrt{n} * \log(n^2) + 10n^2 = Θ(n^2 )$.
(b) Provare che $(n + log(n)) * 3^n = O(\frac{4^n}{n})$.
supponendo che $f(n) = O(g(n))$ provare o confutare che
(a) $log (f (n)) = O(log (g(n)))$
(b) $2 * f (n) = O(2*g(x) )$
(c) $f (n)^2 = O(g(n)^2 )$
il primo esercizio ($5n \sqrt{n} * \log(n^2) + 10n^2 = Θ(n^2 )$.) l'ho risolto per gli altri non so come muovermi.
non cerco la soluzione ma un instradamento verso il risultato
saluti e buone feste!!!
(a) Provare che $5n \sqrt{n} * \log(n^2) + 10n^2 = Θ(n^2 )$.
(b) Provare che $(n + log(n)) * 3^n = O(\frac{4^n}{n})$.
supponendo che $f(n) = O(g(n))$ provare o confutare che
(a) $log (f (n)) = O(log (g(n)))$
(b) $2 * f (n) = O(2*g(x) )$
(c) $f (n)^2 = O(g(n)^2 )$
il primo esercizio ($5n \sqrt{n} * \log(n^2) + 10n^2 = Θ(n^2 )$.) l'ho risolto per gli altri non so come muovermi.
non cerco la soluzione ma un instradamento verso il risultato
saluti e buone feste!!!
Risposte
Ti conviene spiegare il significato dei simboli. $Theta$ sta per... E $O$ sta per...
Tiro ad indovinare: [tex]O[/tex] sta per o grande. E [tex]\Theta[/tex] è la relazione theta che esprime il fatto che il LHS ha lo stesso ordine di grandezza dell'argomento del RHS.
Quanto ho vinto?
Quanto ho vinto?
Per la prima parte prova semplicemente ad applicare la definizione di $O$ e $\Theta$...
il secondo esercizio della prima parte, intuitivamente so che è corretto, però non riesco a formalizzarlo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo