Originariamente inviato da marco vee
quindi la notazione O è riferita ai casi peggiori e omega ai casi migliori?
In *pratica*, sì. Dire che la complessità di un algoritmo sia O(f(n)), dove f(n) è una generica funzione in n (come proprio n o n^2 o nlogn) significa che essa non crescerà mai "più rapidamente" di f(n), quindi appunto che l'algoritmo ha un tempo di esecuzione che è al massimo proporzionale a f(n) (quindi nel caso peggiore). Similmente, se la complessità è Ω(f(n)) si sta dicendo che questa non crescerà mai "più lentamente" di f(n), quindi che anche nel migliore dei casi il tempo di esecuzione dell'algoritmo non potrebbe essere più "lento" di f(n), dove chiaramente, visto che stiamo parlando di funzioni, i concetti di rapidità e lentezza indicano come crescono le funzioni stesse al variare di n.

Comunque non accontentarti di queste spiegazioni superficiali, studia da un libro.