Recorrencia

EQUAÇÕES DE RECORRÊNCIA
Héctor Soza Pollman - Universidade Católica do Norte - Antofagasta, Chile

( Nível Avançado

Frenqüentemente em teoria da Computação (ver exemplo [2]), ao analisar o tempo de execução de um algoritmo (ou o espaço ocupado na memória pelos dados), obtemos uma (ou mais) equações discretas, chamadas de Equações de Recorrência, cuja incógnita é uma função inteira f(n), que geralmente é uma função do tamanho n do problema (por exemplo: a quantidade de dados a ordenar se é um algoritmo de ordenamento). Esta equação resulta ser uma relação entre f(n) e seus valores prévios, como são f(n – 1), f(n / 2), ou outro. Além disso se conhecemos o algoritmo analisado com detalhe, podemos estabelecer um valor de bordo num ponto dado (como f(0) por exemplo). Neste artigo são apresentados alguns dos métodos desenvolvidos para resolver este tipo de equações, as quais aparecem em ordem de dificuldade.

Os tipos de equações de recorrência a serem consideradas são as seguintes, em que a incógnita é a sucessão [pic]com [pic]

1. EQUAÇÃO LINEAR DE PRIMEIRA ORDEM COM COEFICIENTES DE VALOR INTEIRO 1.

O tipo mais simples de equação de recorrência de primeira ordem é:
[pic] , [pic] em que [pic] e a sucessão [pic] são dados do problema. Sua resolução faz uso da propriedade telescópica da soma obtendo:
[pic] [pic]
Exemplo: Para a equação: [pic] com [pic] obtemos [pic]

2. EQUAÇÃO LINEAR DE PRIMEIRA ORDEM COM COEFICIENTES CONSTANTES.

A equação linear de primeira ordem com coeficientes constantes é:
[pic] [pic] em que [pic] e as sucessões numéricas [pic], [pic] e [pic] são dados do problema (as sucessões [pic]e [pic]não devem ser nulas). Para resolver esta equação ela deve ser multiplicada pelo fator [pic] (chamado fator somante):
[pic]
Impõe-se a condição:
[pic] (1) com o qual obtemos:
[pic]

Observa-se que a equação anterior se reduz a uma de primeiro tipo, e que sua solução é:
[pic]

O fator somante é obtido a partir da condição (1) e