Resolvendo uma relação de recorrência usando o método de iteração

Question

Considere este exemplo:

T(n) = T(7n/8) + 2n 

Eu assumi t (1) = 0

e tentou resolvê -lo da seguinte maneira

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)               

Mas não consegui chegar a nenhuma conclusão sobre isso. Estou confuso sobre o que devo fazer na próxima etapa.

Answer 1

Sua abordagem é sólida, mas você verá o que fazer se a reescrever um pouco diferente:

T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

Agora deixe k tende a infinito e ver o que acontece. Ajudaria se você estiver familiarizado com Séries geométricas.

Answer 2

T (n) = t (7n/8) + 2n = 2n * (1 + 7/8 + (7/8)^2 + ... (7/8)^z) + t (1) onde z = ?

O único truque é encontrar Z. Aposto que um log ajudará. Desculpe, é tarde, e eu não estou pensando bem, mas ... você não precisa adicionar vários 2N.

EDIT: Z é quantos vezes você precisa se multiplicar por 7/8 até obter 1.

Então, n * 7^z / 8^z = 1

(7/8)^z = 1/n

(8/7)^z = n

Você quer resolver o Z.

Answer 3

O que você tem lá na última linha é um Séries geométricas E há um Fórmula Para simplificar essa soma.