Lista 8 - Notação Grande O - Matemática Discreta 2021-2

Lista 6 -- Notação Grande O Matemática Discreta -- Prof. Jeroen van de Graaf Leitura recomendada Slides elaborados pelo professor; Rosen 3.2 (3.1, 3.3) Observações e lembretes Simplificação Vc pode supor que a imagem das funções etc é náo-negativo, i.e. , para eliminar o valor absoluto na definição. Teorema Sejam funções de para tal que existe e é igual a . Então, 1. se , então . 2. se , então e . 3. se , considere e aplique (1). Então . Esse teorema é provado no livro do Brassard&Bratley -- Fundamentals of Algorithmics [pg 84], e pode ser usado nos exercícios e nas provas. Notação logaritmo é o logaritmo base 2; é o logaritmo natural, ou seja, de base ; é o logaritmo base 10 na sua calculadora, senão é provavelmente base . Mas pessoalmente prefiro usar para e reservar para . Na notação O(), a base não faz diferença, já que trocar de base é multiplicar por um constante. Exemplo: ; é assim que calculo logaritmos base 2 na calculadora. Questões discursivas 1. Qual é a definição ? 2. O que se sabe sobre a ordem da soma de duas funções? 3. O que se sabe sobre a ordem da soma de dois polinômios? 4. O que se sabe sobre a ordem do produto de duas funções? 5. Explique a notação usando grande . 6. Explique a notação usando grande . 7. Existem vários abusos de notação . Mencione no mínimo dois. Exercícios F=fácil, M=médio, D=difícil (1) [M] 3.2.11 de Rosen (2) [M] 3.2.12 (3) [M] 3.2.19 (4) [M] 3.2.21 (5) [M] Sejam . Prove a transitividade da notação : Se e , então . (6) [M] Nos slides, e simplifiquei a prova de Exemplo 3.2.11 me restingindo a númoros pares. Explique porque isso é permitido. (7) [D] É óbvio que . A questão é se o contrário também é verdade. Ou seja, se e são da mesma ordem, ou se é estritamente maior. (8) [D] Usando apenas o símbolo ou coloque as seguintes ordens de funções numa sequência (ordem): . Aqui é um constante real no intervalo . (9) [D**] Prove que . A dificuldade reside na definição do primeiro e último termo. (10) [D] Mostre que seguindo essas dicas. Suponha que seja par (veja Pergunta 6). (a) Explique porque ; (b) Explique porque