Analise de Algoritmos - Recorrencia e Complexidade Assintotica

4 2 ptos No desenvolvimento de um sistema um analista utilizou um algoritmo que soluciona um problema dividindoo em 2 subproblemas cada uns dos quais com um tamanho 12 do tamanho original Levando um tempo de O1 para dividir o problema em subproblemas e combinar as soluções Se é conhecido que o tempo do algoritmo quando n1 é Tn1 a Defina a relação de recorrência para a solução proposta pelo analista b Resolver a recorrência para obter os limites assintóticos O do algoritmo proposto pelo analista 1 2 ptos Na figura se mostra um algoritmo na linguagem C para incrementar o valor de duas variáveis void p3 int n int i j x y x y 0 for i1 in i for ji jn j x x 1 a Usando a notação Big O e suas propriedades determine a complexidade assintótica do algoritmo b Determine usando somatórios a função que descreve a complexidade do algoritmo Qual é a complexidade assintótica do algoritmo 4 a Tn 1 quando n 1 Tn 2Tn2 O1 quando n 1 b Resolvendo pelo método de substituição assumindo que O1 vale uma constante k qualquer temos Tn 2Tn2 k 22Tn4 k k 4Tnk 3k nT1 Tn 1k nk n 1k 2nk k On Assumindo que Tn c n Começamos com T1 e assumindo que Tn está correto para Tn 1 também estará usando a suposição imposta por Tn 1 a void p3int n int i j x y 1 x y 0 1 for i 0 i n i n for j i j n j n i x 1 Tn 2 n n i 1 1 Tn 2 n n i Tn 2 n² n1 Podemos assumir que esse algoritmo é limitado superiormente por On² b 𝑖 1 𝑛 𝑖 1 𝑗 𝑖 𝑛 𝑗 1 Aqui temos um somatório dentro de outro primeiro executamos o interno para depois realizar a próxima iteração do externo Devido ao fato de que o algoritmo não possui uma condição de parada ele só pode ser limitado superiormente não existe melhor caso nem caso médio Analisando os somatórios podemos concluir que ambos executam em tempo On e já que da forma que foi posto estão criando um produto desses somatórios temos que a complexidade é On²