epdragon ha scritto:
Sia g(n) = n + 2n^3 - 3n^3 + 4n^4. Dire quali delle seguenti affermazioni sono vere e quali sono false. E' necessario provare le affermazioni che si ritengono vere, non è necessario provare le affermazioni che si ritengono false.
(a) g(n) = O(n log n)
(b) g(n) = T(n^5)
(c) g(n) = O(n^10)
(d) g(n) = O(n^4)
So quale sono vere e quali sono false però non so come spiegare le affermazioni vere. Qualche dritta? oppure qualche esercizio svolto simile?
a= Vero - b= Falso - c= Vero - d= Vero
(A) VERO
Da definizione, troviamo N e C tali che per qualsiasi n > N : g(n) >= C*f(n), cioè: n + 2 * n ^ 3 – 3 * n^3 + 4 * n^4 >= C * n * log n
Scegliendo C = 4, deve valere : n * (1 – n^2 + 4*n^3) >= 4 * n * log n, quindi (1 – n^2 + 4*n^3) >= 4 * log n
Poiché log n < n e quindi 4 * log n < 4 * n, l’equazione di sopra è automaticamente vera
per tutti gli n che verificano anche: (1 – n^2 + 4*n^3) >= 4 * n
Poiché (1 – n^2 + 4*n^3) > (– n^2 + 4*n^3), l’equazione di sopra è automaticamente vera
per tutti gli n che verificano anche: (– n^2 + 4*n^3) >= 4 * n,
quindi per tutti gli n che verificano: n * (- n + 4 * n^2) >= 4 * n ===> - n + 4 * n^2 >= 4 ===> n^2 >= 1 + n / 4
Poiché n^2 >= n, la condizione di sopra è vera per tutti gli n tali che n >= 1 + n/4, cioè n >= 4/3
Perciò la condizione iniziale è vera prendendo, ad esempio, C = 4 e N = 2 (o N=3 o N=4… tutti quelli maggiori di 4/3)
(C) VERO
Da definizione, troviamo N e C tali che per qualsiasi n > N : g(n) <= C*f(n), cioè: n + 2 * n ^ 3 – 3 * n^3 + 4 * n^4 <= C * n ^ 10
Scegliendo C = 5, deve valere : n * (1 – n^2 + 4*n^3) <= 5 *n^10, quindi (1 – n^2 + 4*n^3) <= 5 * n^9
Poiché (1 – n^2 + 4*n^3) < (1 + 4*n^3), l’equazione di sopra è automaticamente vera
per tutti gli n che verificano: (1 + 4*n^3) <= 5 * n^9
Poiché n^9 >= n^3 e quindi 5 * n^9 >= 5 * n^3, l’equazione di sopra è automaticamente vera
per tutti gli n che verificano: (1 + 4*n^3) <= 5 * n^3, cioè 1 <= n^3 che è vera sempre
Perciò la condizione iniziale è vera prendendo, ad esempio, C = 5 e N = 1
(D) VERO
Da definizione, troviamo N e C tali che per qualsiasi n > N : g(n) >= C*f(n), cioè: n + 2 * n ^ 3 – 3 * n^3 + 4 * n^4 >= C * n ^ 4
Scegliendo C = 3, deve valere : n * (1 – n^2 + 4*n^3) >= 3 * n^4, quindi (1 – n^2 + 4*n^3) >= 3 * n^3
Poiché (1 – n^2 + 4*n^3) > (– n^2 + 4*n^3), l’equazione di sopra è automaticamente vera
per tutti gli n che verificano: (– n^2 + 4*n^3) >= 3 * n^3, cioè n^3 >= n^2, che è vero sempre
Perciò la condizione iniziale è vera prendendo, ad esempio, C = 3 e N = 1