¿Cuál será la complejidad de T (n) = 2T (n-1) – 1 usando el método de sustitución?

Answer 1

Bien aquí.

[matemática] T (n) = 2T (n-1) – 1 [/ matemática] ………. (1)

[matemáticas] T (n-1) = 2T (n-2) – 1 [/ matemáticas], sustitúyalo en la ecuación número 1

[matemáticas] T (n) = 2 (2T (n – 2) – 1) – 1 = 4T (n – 2) – 2 – 1 = 4T (n – 2) – 3 [/ matemáticas]

Similar,

[matemáticas] T (n) = 4 (2T (n-3) – 1) – 3 = 8T (n-3) – 7 [/ matemáticas]

Avance rápido,

[matemáticas] T (n) = 2 ^ kT (nk) – (2 ^ k-1) [/ matemáticas]

let [math] nk = 1, [/ math] Porque finalmente nk tiene que ser 1 ya que está disminuyendo uno por uno.

[matemáticas] T (n) = 2 ^ k T (1) – (2 ^ k – 1) = 2 ^ k (T (1) – 1) + 1 [/ matemáticas]

[matemáticas] \ implica T (n) = O (2 ^ {k}) = O (2 ^ {n}) [/ matemáticas]

Porque [matemáticas] k = n-1 [/ matemáticas]

Por favor, corrígeme si me equivoco en alguna parte. 🙂