¿Cuál es la complejidad temporal de 2T (n-1) -1?

Answer 1

Relación de recurrencia dada => T (n) = 2T (n − 1) −1

T (n) = 2T (n-1) -1… .. (1)

vamos a encontrar el valor de T (n-1), así que sustituye n por n-1 en la ecuación (1)

T (n-1) = 2T ((n-1) -1) -1
T (n-1) = 2T (n-2) -1… .. (2)
Similar..
T (n-2) = 2T (n-3) -1… .. (3)
T (n-3 = 2T (n-4) -1 … .. (4), y así sucesivamente

Ahora sustituye: – ecuación (2), (3), (4) en la ecuación (1)
T (n) = 2T (n-1) -1
T (n) = 2 [2T (n-2) -1] -1 = 4T (n-2) -2–1 = 4T (n-2) -3
T (n) = 4 [2T (n-3) -1] -3 = 8T (n-3) -4–3 = 8T (n-3) -7
T (n) = 8 [2T (n-4) -1] -7 = 16T (n-4) -8–7 = 16T (n-4) -15

T (n) = 16T (n-4) -15 se puede escribir como,

T (n) = 2 ^ k T (nk) – (2 ^ k – 1)

Dado que el valor de T (n-1) se reduce uno por uno, entonces supongamos
nk = 1 n = k

T (n) = 2 ^ n T (1) – (2 ^ n -1)
Entonces la Complejidad del Tiempo será:

= O (2 ^ n * c – 2 ^ n + 1)

= O (2 ^ n (c-1) +1)

= O (2 ^ n)

Entonces 2 ^ n es la Complejidad del tiempo para una relación de recurrencia dada.