Como provar a complexidade de um algoritmo?

Question

Eu tenho algumas questões sobre analisar complexidade de algoritmo, eu tenho a resposta correta delas(verdadeiro ou falsa),porém não sei como provar, se alguém conseguir me explicar o raciocínio pra chegar a prova real delas:

100n não está em Ω(n²) -> Gabarito diz que é verdadeiro.
n + log n está em Θ(n) -> Gabarito diz que é verdadeiro
Podemos dizer que uma um algoritmo com complexidade f(n)  está em O(f(n/2)). -> Gabarito diz que é falso.
Uma função f(n) domina assintoticamente outra função g(n) se existem duas constantes positivas c e n_0 tais que, para n≥n_0, temos  f(n)≤c∙g(n).Gabarito diz falso.
Para duas funções g(n) e f(n) temos que f(n)=Ω(g(n)) se somente se f(n)=O(g(n)).gabarito diz que é falsa.

Allan Juan · Answer

Em análise assintótica, quem domina é o termo com maior magnitude. Por exemplo, na expressão:
N³ + 1000N² + 10000N + 1000000, quem domina é O N³. Isso pq conforme N vai ao infinito, o valor dos demais termos torna-se irrisório perto de N³.
Então, avaliando as proposições.

1: 100N não está em O(N²): Verdadeiro. 100N está em O(N), pq o expoente do maior termo é 1.
2: N + logN está em O(N): Verdadeiro. N cresce muito mais rápido do que logN e portanto domina a expressão.
5: f(n) = Ω(g(n)) se e somente se f(n) = O(g(n)) => Ω(g(n)) = O(g(n)). O que essa expressão está nos dizendo é que para uma função ser igual ao melhor caso de outra função, também deve ser igual ao pior caso, o que é um absurdo. Basta tomar uma função qualquer que tenha melhor caso diferente do pior caso, que irá contradizer essa proposição, provando sua falsidade.

Na terceira me parece que o gabarito está errado, e a quarta não sei responder. Peço que consulte seu professor e me retorne, também quero saber.
Espero ter ajudado ;)

Como provar a complexidade de um algoritmo?

One Answer

Add your own answers!

Ask a Question