El análisis no es exacto aunque el resultado es correcto. Puede escribirlo con mayor precisión reemplazando $ = $ con $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ dado que no todos los niveles tienen el mismo número de hijos, considere la ruta más diestra, n está disminuyendo $ 2 $ en cada paso).
De hecho, un análisis más cuidadoso puede obtener un límite más estricto como mencionado en el comentario. La idea es que el tiempo $ T (n) $ se calcula con $ T (n-1) + T (n-2) $ de la misma manera que el fibonacci actual $ F (n) $, y dado que $ F (n ) = O (\ phi ^ n) $ para $ \ phi = (1+ \ sqrt {5}) / 2 $ como la forma cerrada.
Por lo tanto $ T (n) = O (\ phi ^ n) $ que es un poco más pequeño que $ 2 ^ n $
Comentarios