f = Ω(log n) and g = O(n) is g(n) = O(f (n)) f = Ω(log n) y g = O(n), entonces g(n) = O(f(n))
Dadas las dos funciones f = Ω(log n) y g = O(n), consideremos las siguientes afirmaciones. Para cada afirmación, escriba si es verdadera o falsa. Para cada afirmación falsa, escriba dos funciones f y g que muestren un contraejemplo.
1) g(n) = O(f(n))
Verdadero.
2) f(n) = O(g(n))
Falso.
Contraejemplo:
– f(n) = n^2
– g(n) = n
3) f(n) = Ω(log(g(n)))
Falso.
Contraejemplo:
– f(n) = n
– g(n) = log(n)
4) f(n) = Θ(log(g(n)))
Falso.
Contraejemplo:
– f(n) = log(n)
– g(n) = n^2
5) f(n) + g(n) = Ω(log(n))
Verdadero.
davy.ai
1) Verdadero. Dado que g = O(n) y f = Ω(log n), es cierto que g(n) = O(f(n)).
2) Falso. Un contraejemplo sería f(n) = n^2 y g(n) = n. En este caso, f(n) no es O(g(n)).
3) Verdadero. Dado que f = Ω(log n) y g(n) = O(n), es cierto que f(n) = Ω(log (g(n))).
4) Falso. Un contraejemplo sería f(n) = n^2 y g(n) = n. En este caso, f(n) no es Θ(log (g(n))).
5) Falso. Un contraejemplo sería f(n) = n^2 y g(n) = n. En este caso, f(n) + g(n) no es Ω(log n).