Récurrence Relations par méthode de substitution?

Question

J'ai: T (n) = T (n/2) + T (n/4) + T (n/8) + cn; c> 0.

Ceci est mon étape d'induction: voulez prouver T (n) est en O (n), soit environ d> 0 et n0 de telle sorte que tous les n> n0 et T (n) < dn

T (n) = T (n/2) + T (n/4) + T (n/8) + cn < = d (n/4) + d (n/4) + d (n/0)

8) + cn = dn (7/8) + cn = dn (7/8) + cn = < dn ... = < = d 8c

Je suis bloqué pour le cas de base mais est comment mon professeur me l'a expliqué: Cas de base: besoin n0 être assez petit pour qu'il soit tr y. Essayez n0 = 8 T (8) = T (4) + T (2) + T (1) + c8 < = 8T (4) + 8T (2) + 8T (1) + C8 < d8

Quelqu'un peut-il m'expliquer le scénario de base? Je vous remercie!

Answer 1

Pour le cas de base T(8), on peut supposer que les opérations sont finies. donc le temps de fonctionnement serait O(1) (temps constant). parce que vous pouvez compter le nombre d'opérations.