Aproximação assintótica de uma relação de recorrência (Akra-Bazzi parece não se aplicar)

Suponha que um algoritmo tenha uma relação de recorrência em tempo de execução:

$T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 \end{array} \right.$

para alguma constante . Suponha que seja polinomial em , talvez quadrático. Muito provavelmente, será exponencial em .$0 < \delta < 1$$g$$n$$f$$n$

Como alguém analisaria o tempo de execução ( seria excelente)? O teorema do mestre e o método mais geral de Akra-Bazzi parecem não se aplicar.$\Theta$

Uma abordagem possível pode ser por analogia com equações diferenciais. Seja . Aqui T ′ ( n ) é um análogo discreto da primeira derivada de T ( n ) . Temos a seguinte relação: T ′ ( n ) = T ( ⌊ δ n ⌋ ) + g ( n ) $T'(n) = T(n)-T(n-1)$$T'(n)$$T(n)$

$$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$$ O análogo contínuo disso é a equação diferencial ou, se você preferir vê-lo escrito de forma diferente: $$t'(x) = t(\delta x) + g(x),$$ Essa é uma equação diferencial. $${d \over dx} t(x) = t(\delta x) + g(x).$$

$t(x)$

Eu esqueci tudo o que sabia sobre equações diferenciais, então não conheço a solução dessa equação diferencial, mas talvez você consiga resolvê-lo revisando todas as técnicas para resolver equações diferenciais.