![Page 1: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/1.jpg)
Analise de AlgoritmosAula 07
Prof. Murilo V. G. da Silva
DINF/UFPR
(material da disciplina: Andre Guedes, Renato Carmo, Murilo da Silva)
![Page 2: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/2.jpg)
Notacao o(1)
Uma funcao f : N→ R e assintoticamente nula se para todo c > 0 existe nc ∈ N talque f (n) em valor absoluto nunca ultrapassa cf de nf em diante, isto e,
|f (n)| ≤ c, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente nulas e denotado por o(1), isto e,
o(1) = f : N→ R | ∀c∃nc , |f (n)| ≤ c, para todo n ≥ nc
O uso de o(1) em igualdades segue convencao analoga ao uso de O(1) em igualdades.
Teorema 29
f (n) = o(1) se e somente se lim f (n) = 0.
Prova: Exercıcio??
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 3: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/3.jpg)
Notacao o(1)
Uma funcao f : N→ R e assintoticamente nula se para todo c > 0 existe nc ∈ N talque f (n) em valor absoluto nunca ultrapassa cf de nf em diante, isto e,
|f (n)| ≤ c, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente nulas e denotado por o(1), isto e,
o(1) = f : N→ R | ∀c∃nc , |f (n)| ≤ c, para todo n ≥ nc
O uso de o(1) em igualdades segue convencao analoga ao uso de O(1) em igualdades.
Teorema 29
f (n) = o(1) se e somente se lim f (n) = 0.
Prova: Exercıcio??
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 4: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/4.jpg)
Notacao o(1)
Uma funcao f : N→ R e assintoticamente nula se para todo c > 0 existe nc ∈ N talque f (n) em valor absoluto nunca ultrapassa cf de nf em diante, isto e,
|f (n)| ≤ c, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente nulas e denotado por o(1), isto e,
o(1) = f : N→ R | ∀c∃nc , |f (n)| ≤ c, para todo n ≥ nc
O uso de o(1) em igualdades segue convencao analoga ao uso de O(1) em igualdades.
Teorema 29
f (n) = o(1) se e somente se lim f (n) = 0.
Prova: Exercıcio??
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 5: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/5.jpg)
Notacao o(1)
Uma funcao f : N→ R e assintoticamente nula se para todo c > 0 existe nc ∈ N talque f (n) em valor absoluto nunca ultrapassa cf de nf em diante, isto e,
|f (n)| ≤ c, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente nulas e denotado por o(1), isto e,
o(1) = f : N→ R | ∀c∃nc , |f (n)| ≤ c, para todo n ≥ nc
O uso de o(1) em igualdades segue convencao analoga ao uso de O(1) em igualdades.
Teorema 29
f (n) = o(1) se e somente se lim f (n) = 0.
Prova: Exercıcio??
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 6: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/6.jpg)
Notacao o(1)
Uma funcao f : N→ R e assintoticamente nula se para todo c > 0 existe nc ∈ N talque f (n) em valor absoluto nunca ultrapassa cf de nf em diante, isto e,
|f (n)| ≤ c, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente nulas e denotado por o(1), isto e,
o(1) = f : N→ R | ∀c∃nc , |f (n)| ≤ c, para todo n ≥ nc
O uso de o(1) em igualdades segue convencao analoga ao uso de O(1) em igualdades.
Teorema 29
f (n) = o(1) se e somente se lim f (n) = 0.
Prova: Exercıcio??
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 7: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/7.jpg)
Notacao o(f (n))
Dizemos que g(n) e assintoticamente muito menor que f (n) se para todo c > 0 existenc ∈ N tal que
|g(n)| ≤ c|f (n)|, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente muito menores do que f (n) e denotado poro(f (n)), isto e,
o(f (n)) = g : N→ R | ∀c∃nc , |g(n)| ≤ c|f (n)|, para todo n ≥ nc
Teorema 30
Se
g(n) = o(f (n)), e
f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N,
entaog(n) = o(1)f (n).
Teorema 31
Se g(n) = o(1)f (n) entao g(n) = o(f (n)) e, alem disso,f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 8: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/8.jpg)
Notacao o(f (n))
Dizemos que g(n) e assintoticamente muito menor que f (n) se para todo c > 0 existenc ∈ N tal que
|g(n)| ≤ c|f (n)|, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente muito menores do que f (n) e denotado poro(f (n)), isto e,
o(f (n)) = g : N→ R | ∀c∃nc , |g(n)| ≤ c|f (n)|, para todo n ≥ nc
Teorema 30
Se
g(n) = o(f (n)), e
f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N,
entaog(n) = o(1)f (n).
Teorema 31
Se g(n) = o(1)f (n) entao g(n) = o(f (n)) e, alem disso,f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 9: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/9.jpg)
Notacao o(f (n))
Dizemos que g(n) e assintoticamente muito menor que f (n) se para todo c > 0 existenc ∈ N tal que
|g(n)| ≤ c|f (n)|, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente muito menores do que f (n) e denotado poro(f (n)), isto e,
o(f (n)) = g : N→ R | ∀c∃nc , |g(n)| ≤ c|f (n)|, para todo n ≥ nc
Teorema 30
Se
g(n) = o(f (n)), e
f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N,
entaog(n) = o(1)f (n).
Teorema 31
Se g(n) = o(1)f (n) entao g(n) = o(f (n)) e, alem disso,f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 10: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/10.jpg)
Notacao o(f (n))
Dizemos que g(n) e assintoticamente muito menor que f (n) se para todo c > 0 existenc ∈ N tal que
|g(n)| ≤ c|f (n)|, para todo n ≥ nc .
O conjunto o(1)
O conjunto das funcoes assintoticamente muito menores do que f (n) e denotado poro(f (n)), isto e,
o(f (n)) = g : N→ R | ∀c∃nc , |g(n)| ≤ c|f (n)|, para todo n ≥ nc
Teorema 30
Se
g(n) = o(f (n)), e
f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N,
entaog(n) = o(1)f (n).
Teorema 31
Se g(n) = o(1)f (n) entao g(n) = o(f (n)) e, alem disso,f (n) = 0 =⇒ g(n) = 0, para todo n ∈ N.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 11: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/11.jpg)
Notacao o(1) e o(f (n))
Notacao para “muito menor” e “aproximadamente”:
g(n) f (n) = g(n) = o(f (n)),
g(n) ≈ f (n) = g(n) = (1 + o(1))f (n).
Teorema 32
Se f (n) = O(1) e g(n) = o(1), entao f (n)g(n) = o(1), isto e,
O(1)o(1) = o(1).
Prova
Exercıcio 36.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 12: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/12.jpg)
Notacao o(1) e o(f (n))
Notacao para “muito menor” e “aproximadamente”:
g(n) f (n) = g(n) = o(f (n)),
g(n) ≈ f (n) = g(n) = (1 + o(1))f (n).
Teorema 32
Se f (n) = O(1) e g(n) = o(1), entao f (n)g(n) = o(1), isto e,
O(1)o(1) = o(1).
Prova
Exercıcio 36.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 13: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/13.jpg)
Notacao o(1) e o(f (n))
Notacao para “muito menor” e “aproximadamente”:
g(n) f (n) = g(n) = o(f (n)),
g(n) ≈ f (n) = g(n) = (1 + o(1))f (n).
Teorema 32
Se f (n) = O(1) e g(n) = o(1), entao f (n)g(n) = o(1), isto e,
O(1)o(1) = o(1).
Prova
Exercıcio 36.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 14: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/14.jpg)
Notacao o(1) e o(f (n))
Notacao para “muito menor” e “aproximadamente”:
g(n) f (n) = g(n) = o(f (n)),
g(n) ≈ f (n) = g(n) = (1 + o(1))f (n).
Teorema 32
Se f (n) = O(1) e g(n) = o(1), entao f (n)g(n) = o(1), isto e,
O(1)o(1) = o(1).
Prova
Exercıcio 36.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 15: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/15.jpg)
Notacao o(1) e o(f (n))
Notacao para “muito menor” e “aproximadamente”:
g(n) f (n) = g(n) = o(f (n)),
g(n) ≈ f (n) = g(n) = (1 + o(1))f (n).
Teorema 32
Se f (n) = O(1) e g(n) = o(1), entao f (n)g(n) = o(1), isto e,
O(1)o(1) = o(1).
Prova
Exercıcio 36.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 16: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/16.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 17: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/17.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 18: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/18.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 19: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/19.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n
=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 20: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/20.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 21: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/21.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 22: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/22.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 23: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/23.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,
B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 24: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/24.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 25: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/25.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,
B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 26: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/26.jpg)
Notacao o(1) e o(f (n))
Exemplo 54
Dos Exemplos 39 e 22 temos, respectivamente,
S+(n) = Ω(n), e
B+(n) = O(log n)
Consequentemente,
B+(n)
S+(n)=O(log n)
Ω(n)
T.10, T.17=
O(1) log n
Ω(1)n=O(1)
Ω(1)
log n
n
Ex.37= O(1)o(1)
T.32= o(1),
Portanto,B+(n) = o(S+(n)),
Ou seja,B+(n) S+(n).
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 27: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/27.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja, (n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)= (1 + o(1))
√2π,
Ou seja,s(n) ≈
√2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 28: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/28.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja,
(n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)= (1 + o(1))
√2π,
Ou seja,s(n) ≈
√2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 29: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/29.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja, (n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)= (1 + o(1))
√2π,
Ou seja,s(n) ≈
√2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 30: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/30.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja, (n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)
= (1 + o(1))√
2π,
Ou seja,s(n) ≈
√2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 31: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/31.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja, (n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)= (1 + o(1))
√2π,
Ou seja,s(n) ≈
√2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 32: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/32.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja, (n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)= (1 + o(1))
√2π,
Ou seja,
s(n) ≈√
2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 33: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/33.jpg)
Notacao o(1) e o(f (n))
Exemplo 55: Coeficiente binomial
Do Exemplo 17 temos(n2
)=
n2
2+O(n) =
n2
2
(1 +O(n)
n2/2
)T.10=
n2
2
(1 +O(1)n
n2/2
)=
n2
2
(1 +O(1)
1/2
n
n2
)=
n2
2(1 +O(1)o(1))
T.32=
n2
2(1 + o(1)) ,
Ou seja, (n2
)≈
n2
2.
Exemplo 56: Stirling
Do Exemplo 3 temos
s(n) =√
2π
(1 +
1
12n+
1
288n2−
139
51840n3−
571
2488320n4+ . . .
)= (1 + o(1))
√2π,
Ou seja,s(n) ≈
√2π.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 34: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/34.jpg)
Notacao o(1) e o(f (n))
Exemplo 57
Dos Exemplos 5 e 56 temos
n! = s(n)(ne
)n+1/2= (1 + o(1))
√2πn
(ne
)n,
Consequentemente, para todo b > 1,
logb n! = n logb n − n logb e +1
2logb n + logb(1 + o(1))
= n logb n − n logb e +1
2logb n + o(1),
Equivalentemente,
logb n!−(n logb n − n logb e +
1
2logb n
)= o(1),
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 35: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/35.jpg)
Notacao o(1) e o(f (n))
Exemplo 57
Dos Exemplos 5 e 56 temos
n! = s(n)(ne
)n+1/2= (1 + o(1))
√2πn
(ne
)n,
Consequentemente, para todo b > 1,
logb n! = n logb n − n logb e +1
2logb n + logb(1 + o(1))
= n logb n − n logb e +1
2logb n + o(1),
Equivalentemente,
logb n!−(n logb n − n logb e +
1
2logb n
)= o(1),
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 36: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/36.jpg)
Notacao o(1) e o(f (n))
Exemplo 57
Dos Exemplos 5 e 56 temos
n! = s(n)(ne
)n+1/2= (1 + o(1))
√2πn
(ne
)n,
Consequentemente, para todo b > 1,
logb n! = n logb n − n logb e +1
2logb n + logb(1 + o(1))
= n logb n − n logb e +1
2logb n + o(1),
Equivalentemente,
logb n!−(n logb n − n logb e +
1
2logb n
)= o(1),
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 37: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/37.jpg)
Notacao o(1) e o(f (n))
Exemplo 57
Dos Exemplos 5 e 56 temos
n! = s(n)(ne
)n+1/2= (1 + o(1))
√2πn
(ne
)n,
Consequentemente, para todo b > 1,
logb n! = n logb n − n logb e +1
2logb n + logb(1 + o(1))
= n logb n − n logb e +1
2logb n + o(1),
Equivalentemente,
logb n!−(n logb n − n logb e +
1
2logb n
)= o(1),
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 38: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/38.jpg)
Notacao o(1) e o(f (n))
Exemplo 57
Dos Exemplos 5 e 56 temos
n! = s(n)(ne
)n+1/2= (1 + o(1))
√2πn
(ne
)n,
Consequentemente, para todo b > 1,
logb n! = n logb n − n logb e +1
2logb n + logb(1 + o(1))
= n logb n − n logb e +1
2logb n + o(1),
Equivalentemente,
logb n!−(n logb n − n logb e +
1
2logb n
)= o(1),
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 39: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/39.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − n logb e +1
2logb n + o(1)
= n logb n − n logb e +
(1 +
o(1)
logb n
)1
2logb n
Ex. ??= n logb n − n logb e + (1 + o(1))
1
2logb n,
Ou, menos precisamente,
logb n! = n logb n − n logb e + (1 + o(1))1
2logb n
= n logb n − n logb e
(1 +
1 + o(1)12
logb n
)Ex. ??
= n logb n − (1 + o(1))n logb e,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 40: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/40.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − n logb e +1
2logb n + o(1)
= n logb n − n logb e +
(1 +
o(1)
logb n
)1
2logb n
Ex. ??= n logb n − n logb e + (1 + o(1))
1
2logb n,
Ou, menos precisamente,
logb n! = n logb n − n logb e + (1 + o(1))1
2logb n
= n logb n − n logb e
(1 +
1 + o(1)12
logb n
)Ex. ??
= n logb n − (1 + o(1))n logb e,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 41: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/41.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − n logb e +1
2logb n + o(1)
= n logb n − n logb e +
(1 +
o(1)
logb n
)1
2logb n
Ex. ??= n logb n − n logb e + (1 + o(1))
1
2logb n,
Ou, menos precisamente,
logb n! = n logb n − n logb e + (1 + o(1))1
2logb n
= n logb n − n logb e
(1 +
1 + o(1)12
logb n
)Ex. ??
= n logb n − (1 + o(1))n logb e,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 42: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/42.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − n logb e +1
2logb n + o(1)
= n logb n − n logb e +
(1 +
o(1)
logb n
)1
2logb n
Ex. ??= n logb n − n logb e + (1 + o(1))
1
2logb n,
Ou, menos precisamente,
logb n! = n logb n − n logb e + (1 + o(1))1
2logb n
= n logb n − n logb e
(1 +
1 + o(1)12
logb n
)Ex. ??
= n logb n − (1 + o(1))n logb e,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 43: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/43.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − n logb e +1
2logb n + o(1)
= n logb n − n logb e +
(1 +
o(1)
logb n
)1
2logb n
Ex. ??= n logb n − n logb e + (1 + o(1))
1
2logb n,
Ou, menos precisamente,
logb n! = n logb n − n logb e + (1 + o(1))1
2logb n
= n logb n − n logb e
(1 +
1 + o(1)12
logb n
)Ex. ??
= n logb n − (1 + o(1))n logb e,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 44: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/44.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − (1 + o(1))n logb e
= n logb n
(1−
(1 + o(1))n logb e
n logb n
)= n logb n
(1−
(1 + o(1)) logb e
logb n
)= (1 + o(1))n logb n,
Ou seja,logb n! ≈ n logb n, para todo b > 1.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 45: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/45.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − (1 + o(1))n logb e
= n logb n
(1−
(1 + o(1))n logb e
n logb n
)= n logb n
(1−
(1 + o(1)) logb e
logb n
)= (1 + o(1))n logb n,
Ou seja,logb n! ≈ n logb n, para todo b > 1.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 46: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/46.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − (1 + o(1))n logb e
= n logb n
(1−
(1 + o(1))n logb e
n logb n
)= n logb n
(1−
(1 + o(1)) logb e
logb n
)= (1 + o(1))n logb n,
Ou seja,
logb n! ≈ n logb n, para todo b > 1.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 47: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/47.jpg)
Notacao o(1) e o(f (n))
Exemplo 57 (cont.)
Ou, menos precisamente,
logb n! = n logb n − (1 + o(1))n logb e
= n logb n
(1−
(1 + o(1))n logb e
n logb n
)= n logb n
(1−
(1 + o(1)) logb e
logb n
)= (1 + o(1))n logb n,
Ou seja,logb n! ≈ n logb n, para todo b > 1.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 48: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/48.jpg)
Notacao o(1) e o(f (n))
Exemplo58: Soma Harmonica
Do Exemplo 7 temos
H(n) = ln n +O(1)
=
(1 +O(1)
ln n
)ln n
Ex.??= (1 + o(1)) ln n,
Ou seja,H(n) ≈ ln n.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 49: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/49.jpg)
Notacao o(1) e o(f (n))
Exemplo58: Soma Harmonica
Do Exemplo 7 temos
H(n) = ln n +O(1) =
(1 +O(1)
ln n
)ln n
Ex.??= (1 + o(1)) ln n,
Ou seja,H(n) ≈ ln n.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 50: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/50.jpg)
Notacao o(1) e o(f (n))
Exemplo58: Soma Harmonica
Do Exemplo 7 temos
H(n) = ln n +O(1) =
(1 +O(1)
ln n
)ln n
Ex.??= (1 + o(1)) ln n,
Ou seja,H(n) ≈ ln n.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 51: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/51.jpg)
Notacao o(1) e o(f (n))
Exemplo58: Soma Harmonica
Do Exemplo 7 temos
H(n) = ln n +O(1) =
(1 +O(1)
ln n
)ln n
Ex.??= (1 + o(1)) ln n,
Ou seja,
H(n) ≈ ln n.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 52: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/52.jpg)
Notacao o(1) e o(f (n))
Exemplo58: Soma Harmonica
Do Exemplo 7 temos
H(n) = ln n +O(1) =
(1 +O(1)
ln n
)ln n
Ex.??= (1 + o(1)) ln n,
Ou seja,H(n) ≈ ln n.
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 53: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/53.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!
=n∑
i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 54: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/54.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!=
n∑i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 55: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/55.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!=
n∑i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 56: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/56.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!=
n∑i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 57: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/57.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!=
n∑i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 58: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/58.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!=
n∑i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos
![Page 59: Análise de Algoritmos Aula 07 - UFPR · 2019. 9. 5. · An alise de Algoritmos Aula 07 Prof. Murilo V. G. da Silva DINF/UFPR (material da disciplina: Andr e Guedes, Renato Carmo,](https://reader036.vdocumento.com/reader036/viewer/2022071503/6122b6358289916cdf2395ad/html5/thumbnails/59.jpg)
Notacao o(1) e o(f (n))
Exemplo 59: Serie de Taylor
Do Exemplo 8 temos, para todo x ∈ R e todo n ∈ N,
ex =n∑
i=0
x i
i!+O(1)
xn+1
(n + 1)!=
n∑i=0
x i
i!+O(1)o(1)
Ex.??=
n∑i=0
x i
i!+ o(1),
Ou seja,
ex −n∑
i=0
x i
i!= o(1), para todo x ∈ R,
Ou, menos precisamente,
ex ≈n∑
i=0
x i
i!, para todo x ∈ R,
Prof. Murilo V. G. da Silva Analise de Algoritmos