Comment calculer le temps de fonctionnement de l'algorithme de Karatsuba?

Question

Je sais que la formule est T (n) = 3T (n/2) + O (n), et en utilisant la méthode maître, je peux obtenir le T (n) = n^(log3) avec 2 étant la base.

Mais je ne sais toujours pas comment obtenir la réponse sans utiliser la méthode maître. Parce que le résultat que je reçois de la formule récursive est T (n) = 3^(logn) avec 2 étant la base.

Je serais tellement apprécié si quelqu'un peut m'aider!

Answer 1

Eh bien C'est parce que vous avez tous les deux raison en même temps.

n^(log3) = 3^(logn) 

Preuve:

y = 3^log(n) 
log(y) = log(n)*log(3) 
log(y)/log(n) = log(3) 

log<sub>n</sub>y = log(3)

y = n^(log3)