Ciao a tutti,
avrei bisogno di una mano con lo studio delle complessità degli algoritmi per essere in grado di rispondere a domande come queste:
Siano f(n) e g(n) le complessità dell'algoritmo Chang & Roberts nel caso migliore e nel caso medio, rispettivamente. Quale delle seguenti relazioni asintotiche è falsa?
a) f(n) = Θ(g(n)) b) f(n) = O(g(n)) c) f(n) = o(g(n)) d) g(n) = Ω(g(n))
Siano f(n) e g(n) le complessità dell'algoritmo Chang & Roberts nel caso peggiore e nel caso medio, rispettivamente. Quale delle seguenti relazioni asintotiche è falsa?
a) f(n) = Θ(g(n)) b) f(n) = Ω(g(n)) c) f(n) = !(g(n)) d) f(n) = O(g(n))
Dove le complessità dell'algoritmo Chang & Roberts sono:
Θ(n^2) caso pessimo
Θ(n) caso ottimo
Θ(n log n) caso medio
La risposta alla prima domanda è la a, le risposte per la seconda sono a,d.
Conosco le differenze (a livello di definizioni) tra Θ,O e Ω ma non riesco ad applicarle su domande come queste.
Riuscite ad aiutarmi?