Estruturas de Dados Programação 2 COMP208 Lista de Exercícios Algoritmos e Complexidade Márcio Ribeiro Universidade Federal de Alagoas UFAL Instituto de Computação IC 11 de abril de 2014 Questão 1 Mostre por definição que fn 2n² 3n 4 é On² Questão 2 Mostre por definição que fn n³ não é On² Questão 3 Mostre que 2n1 é O2n Questão 4 Escreva a equação de recorrência da busca linearsequencial Em seguida resolvaa Questão 5 Escreva a equação de recorrência da busca binária Em seguida resolvaa Questão 6 Escreva a equação de recorrência do melhor caso do Quicksort Em seguida resolvaa Questão 7 Prove que fn gn Omaxfn gn
