A notação O, juntamente com outras duas notações complementares (ômega e teta), possibilita descrever o comportamento assintótico de funções de man...
A notação O, juntamente com outras duas notações complementares (ômega e teta), possibilita descrever o comportamento assintótico de funções de maneira precisa. Sejam as funções f(n) = 6n2 e g(n) = n2log2(n), assinale a alternativa que expressa corretamente a relação assintótica entre as duas funções. É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)). Para isso, é preciso provar que existem c e m positivos tais que, para todo n > m, é verdadeiro que f(n) <= cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2, tem-se que 6 <= clog2(n). Tomando-se c = 6 e m = 1, essa desigualdade é satisfeita. Portanto, g(n) é limite superior para f(n). Resta verificar se g(n) também é um limite superior para f(n). Nesse caso, seria verdadeiro que n2log2(n) <= c'6n2, com c' positivo e n > m' > 0. De maneira análoga, obtém-se que og2(n) <= 6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'. Portanto, g(n) não é um limite superior para f(n). Consequentemente, g(n) também não é um limite justo para f(n). A. g(n) é um limite superior para f(n). B. g(n) é um limite justo para f(n). C. f(n) é um limite superior para g(n). D. f(n) é um limite justo para g(n). E. g(n) é um limite superior para f(n).
Compartilhar