Originariamente inviato da GIULIOS
1) Ho una lista di funzioni e devo partizionarle in insiemi, rispettando la condizione
che prese due funzioni dall' insieme f(n) e g(n) vale la condizione
f(n) = teta (g(n)).

Ho gia la soluzione dell'esercizio. Ho un dubbio su questo insieme.

A={log(n!/2^n)^4, log(n!), n log(n + 2)3, 8n log 3√n}

Non ho capito perchè mette le prime due funzioni (fattoriale) nell' insieme con
le funz. di tipo n log n.
Il fattoriale non deve impressionarti dato che log(n!) si può ridurre di fatto a log(n): abbiamo infatti

log(n!) = log(1*2*...*(n-1)*n)

per le proprietà dei logaritmi puoi scriverlo come una somma di logaritmi:

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

quantità che è sicuramente O(log(n)).
Intuitivamente, seppure è vero che n! generalmente è "molto più grande" di n, è pur vero che il logaritmo "abbatte" il valore del proprio argomento, ecco perché in fin dei conti log(n) cresce più o meno come log(n!).

Se oltre a questo poi ricordi altre proprietà tipo che il logaritmo di un rapporto si può scrivere come la differenza tra il logaritmo del numeratore e quello del denominatore o anche che un eventuale esponente dell'argomento del logaritmo può essere "spostato" come costante moltiplicativa del logaritmo stesso, evidentemente puoi ricondurre i primi due alla stessa "forma" degli altri due. Non ho tempo per fare calcoli, provaci.

Originariamente inviato da GIULIOS
2) Ho questa funzione f(n)=(n^3+n)/(n log^2 n+log n).
A sinistra ho una lista di funzioni, devo associare alla funzione di
sopra f(n) una funzione che sia omega di f(n), ma che tra tutte quelle che
sono omega deve essere quella che cresce piu velocemente.
A destra o una altra lista dove devo prendere la funione O grande di f(n)
che cresce piu lentamente rispetto alle altre ma che rimane cmq O grande di
f(n).

Ti enuncio quelle della lista di sinistra su cui sono incerto:
omega(n^1.000001),omega(n^2/log^2 n),omega(n^2/log n),omega(n^3/2).
Le ultime due non credo siano omega di f(n), sono incerto sulle prime due !
Per O grande le funzioni sono le stesse.
Mi dispiace qui non mi viene nessuna idea, d'altra parte è un po' che non tratto queste cose. Hai qualche altro elemento?

Originariamente inviato da Pastore12
Però ho un dubbio che maggiormente mi preme: non è fastidiosamente tecnico?
Questo genere di domande di solito le postano in "programmazione" (in altre sezioni non so, lì capita a volte); in genere le tollerano, altre volte le chiudono perché le considerano "Off topic". E al nostro amico è andata proprio così. Per quanto "programmazione" non sembra la sezione giusta per certe domande, di sicuro altre sezioni più indicate non ce ne sono credo, quindi alla fine la domanda o la fai in OT oppure semplicemente non trova luogo su questo forum.