Quando temos que resolver um problema e, quando são várias as formas disponíveis para resolver o problema (por exemplo de Matriz de cadeia de problema de multiplicação), em que a análise do tempo do algoritmo é necessário.

Análise de algoritmos significa estimar sua complexidade em um sentido assintótico. O termo “análise de algoritmos” foi cunhado por Donald Knuth. Análise de algoritmos é a determinação da quantidade de tempo e recursos espaciais necessários para executá-lo.

A maioria dos algoritmos são recursivos na natureza, eles usam a estratégia de dividir para conquistar. O algoritmo recursivo se chama para as outras entradas. Isso é normalmente parte da entrada original, mas tem um tamanho menor (sub-problema). Há muitas maneiras de resolver a relação de recorrência. São os seguintes:

1. Teorema mestre

2. Método da árvore de recorrência

3. Método de substituição

4. Change of variable method

entre todos estes métodos o teorema mestre é o método mais rápido para encontrar a complexidade temporal da função. É muito fácil de entender e fácil de aplicar. Só temos de nos lembrar de alguns casos. Aqui vamos nós.