Cálculo da complexidade exata de algoritmos do tipo Divisão-e-Conquista via Maple

Abstract

A equação de complexidade de um algoritmo recursivo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõe-se um esquema de solução de equações de recorrência (lineares e do tipo divisão-e-conquista) resolvidas através do aplicativo matemático Maple, resultando em uma expressão algébrica exata para a complexidade. Desenvolveu-se um procedimento no Maple (bloco de comandos) para a solução destas equações de recorrência. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista utilizando o aplicativo matemático Maple.