Como resolver a complexidade recursiva para t (n) = t (n/2) + 2^n pelo método de iteração?

Question

Estou tentando encontrar o limite superior e o limite inferior, que provavelmente é O (2^n)

T (n) = 1 para n <= 4

Eu sei que o órgão geral é:

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

---

daqui não sei como proceder ..

Answer 1

Há algum problema com sua notação. O órgão geral deve ser:

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

Após esta etapa, deixamos i = log(2, n) - 1, para que T(n/2^(i+1)) = T(1).

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

Observe que sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) é 2^n + 2^(n/2) + 2^(n/4) + ..., que é menor que 2^n + 2^(n-1) + 2^(n-2) + .... No entanto, o último material é 2^(n+1) - 1. Então as coisas anteriores são algo entre 2^n e 2^(n+1). Portanto, o soma é O(2^n).

Então T(n) = O(2^n).