Eʼ possibile che un algoritmo abbia tempo di esecuzione O(n2) nel caso peggiore e Ω(n)
nel caso migliore?
Se un algoritmo ha tempo di esecuzione Ω(n2) nel caso peggiore, è possibile che nel caso
migliore lʼalgoritmo abbia complessità O(n log n)?
Se un algoritmo ha tempo di esecuzione Ω(n) e O(n) nel caso peggiore, possiamo
concludere che nel caso peggiore è Θ(n)?
Se la complessità di un problema è Ω(n2) nel caso peggiore, e si dispone di un algoritmo
che risolve il problema in tempo O(n2) nel caso peggiore, si può affermare che lʼalgoritmo
ha tempo di esecuzione Θ(n2) nel caso peggiore?