Encontrar la caja base para T (N)= T (N - A) + T (A) + CN

Question

Estaba resolviendo la recurrencia utilizando el método de árbol de recursión: $$ T (N)= T (N - A) + T (A) + CN $$

Cuando comencé a resolver, podría concluir fácilmente el hecho de que $ t (a) $ tendría un cómputo de costo total en forma de:

$$ h * ca $$ Pero no pude averiguar cómo resolver el caso base.

Sé que $ t (na) $ estaría en el caso de la base cuando $ n= A $ .

Pero cómo calcular la altura $ H $ de la recurrencia. Sé que el caso base se puede definir como: $$ N-IA= 0 $$

He visto los ejemplos anteriores en el libro Introducción a los algoritmos que cotizaciones:

El tamaño del subproblema para un nodo en profundidad $ i $ es $ n / 4 ^ i $ . Por lo tanto, la Tamaño del subproblema Hits $ n= 1 $ cuando $ n / 4 ^ i= 1 $ o, equivalentemente, Cuando $ i=log_4 n $

para la recurrencia: $ t (n)= 3T (n / 4) + cn ^ 2 $

Entonces, llegando al punto. ¿Cuál sería el caso base de tal manera que el tamaño del sub-problema llegue a $ n=? $ como en el ejemplo anterior.

¿Sería $ n= a $ ?

Por favor corríjame si estoy equivocado. Gracias.

Answer 1

Cada $ 0 \ le k \ le a $ produce el caso base $ t (k) $ . Si está tratando de resolver el BIG-O de la recurrencia, entonces también puede asumir que hay algunos $ C $ donde $ T (k) \ le c $ para cada caso base $ k $ .Ayudará a hacer el cálculo un poco más fácil