Cómo resolver esta recurrencia T (n) = T (7n / 10) + n

Answer 1

Un buen árbol de recursión puede ayudar a comprender visualmente.

Como puede ver, la función [matemática] T (n) [/ matemática] conduce a la siguiente función, [matemática] T (7n / 10) [/ matemática] así como [matemática] n [/ matemática]. Entonces podemos seguir construyendo el árbol desde [math] T (7n / 10) [/ math] tan profundo como queramos.

Pero…. no necesitamos ir tan lejos, ya que podemos observar que en cada subproblema en el lado derecho del árbol, gastamos [matemática] n [/ matemática] trabajo. En cada próxima iteración, gastamos [matemática] 7n / 10 [/ matemática] trabajo. Entonces, podemos resumir el árbol como una serie geométrica infinita:

[matemáticas] T (n) = n + n * (7/10) + n * (7/10) ^ 2 + n * (7/10) ^ 3 + n * (7/10) ^ 4 +… [ /matemáticas]

O,

[matemáticas] T (n) = n (1+ (7/10) + (7/10) ^ 2 + (7/10) ^ 3 +…) [/ matemáticas]

Usando la fórmula de secuencia geométrica,

[matemática] T (n) = n * 1 / (1-r) [/ matemática] donde r es la razón común, 7/10

Obtenemos:

[matemáticas] T (n) = n * 1 / (1-7 / 10) = n * 1 / 0.3 => [/ matemáticas]

[matemáticas] 10 / 3n [/ matemáticas].

Answer 2

Este problema se puede resolver utilizando el teorema del maestro:

Answer 3

Aquí a = 1, b = 7, k = 1

a es menor que b potencia k, entonces seguimos la fórmula es decir

T (n) = ϴ (n ^ k log ^ pn)

T (n) = ϴ (n ^ 1 log ^ 0 n)

T (n) = ϴ (n)