¿Cómo resolver la complejidad recursiva para t (n) = t (n/2) + 2^n por método de iteración?

Question

Estoy tratando de encontrar el límite superior y el límite inferior, que probablemente sea o (2^n)

T (n) = 1 para n <= 4

Sé que el órgano general es:

T (n) = t (n/2^(i + 1)) + suma de i = 0 a k de 2^(n/2^i)

---

Desde aquí no sé cómo proceder ..

Answer 1

Hay algún problema con su notación. El órgano general debe ser:

T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)

Después de este paso, dejamos i = log(2, n) - 1, de modo que T(n/2^(i+1)) = T(1).

Por lo tanto, T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k).

Tenga en cuenta que sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) es 2^n + 2^(n/2) + 2^(n/4) + ..., que es más pequeño que 2^n + 2^(n-1) + 2^(n-2) + .... Sin embargo, las últimas cosas son 2^(n+1) - 1. Entonces las cosas anteriores son algo entre 2^n y 2^(n+1). Por lo tanto, los suma es O(2^n).

Después T(n) = O(2^n).