Notazione asintotica, algoritmi

[plesyo96]

Salve,
ho da poco iniziato il corso di Algoritmi e stiamo affrontando la notazione asintotica, partendo dai limiti superiori e inferiori ai problemi computazionali. Sul mio libro c'è scritto:

Per un dato problema computazionale $\Pi$, consideriamo un qualunque algoritmo A di risoluzione. Se A richiede $t(n)$ tempo per risolvere una generica istanza di $\Pi$ di dimensione n, diremo che $O(t(n))$ è un limite superiore alla complessità in tempo del problema $\Pi$. Lo scopo del progettista è quello di riuscire a trovare l'algoritmo A con il migliore tempo $t(n)$ possibile. A tal fine, quando riusciamo a dimostrare con argomentazioni combinatorie che qualunque algoritmo A' richiede almeno tempo $f(n)$ per risolvere II su un'istanza generica di dimensione n, asintoticamente per infiniti valori di n, diremo che $\Omega(f(n))$ è un limite inferiore alla complessità in tempo del problema $\Pi$. In tal caso, nessun algoritmo può richiedere asintoticamente meno di $O(f(n))$ tempo per risolvere $\Pi$. Ne deriva che l'algoritmo A è ottimo se $t(n) = O(f(n))$, ovvero se la complessità in tempo di A corrisponde dal punto di vista asintotico al limite inferiore di $\Pi$.

Ciò che non mi convince è: ma A non è ottimo se $t(n)=\Omega(f(n))$? Inoltre non è più corretto dire:
nessun algoritmo può richiedere asintoticamente meno di $\Omega(f(n))$ tempo per risolvere $\Pi$?

È un errore del libro o mi sfugge qualcosa?

[vict85]

Si, direi che hai ragione tu.

[plesyo96]

"vict85":Si, direi che hai ragione tu.

Non sono convinto. Se $\Omega(f(n))$ è un limite inferiore alla complessità in tempo del problema, allora $O(f(n))$ è l'insieme di tutte le funzioni che sono al di sotto (o sono uguali) alla funazione $f(n)$ (in realtà moltiplicata per una costante positiva). Quindi se $t(n)$ (abbiamo supposto che sia la complessità in tempo di un algoritmo generico A), è al di sotto di $f(n)$ allora è ottimo. Forse è questa l'interpretazione?? Perchè non credo sia un errore, questo pezzo è stato riportato anche nelle edizioni successive. Anche se il mio ragionamento fosse giusto, non riesco a capire la frase:
"nessun algoritmo può richiedere asintoticamente meno di $O(f(n))$ tempo per risolver $\Pi$".