Come risolvere la complessità ricorsiva per t (n) = t (n/2) + 2^N con metodo di iterazione?

Question

Sto cercando di trovare il limite superiore e il limite inferiore, che probabilmente è O (2^n)

T (n) = 1 per n <= 4

So che l'organo generale è:

T (n) = t (n/2^(i + 1)) + somma da i = 0 a k di 2^(n/2^i)

---

Da qui non so come procedere ..

Answer 1

C'è qualche problema con la tua notazione. L'organo generale dovrebbe essere:

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

Dopo questo passaggio, lasciamo i = log(2, n) - 1, affinché T(n/2^(i+1)) = T(1).

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

Notare che sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) è 2^n + 2^(n/2) + 2^(n/4) + ..., che è più piccolo di 2^n + 2^(n-1) + 2^(n-2) + .... Tuttavia, quest'ultima roba è 2^(n+1) - 1. Quindi l'ex roba è qualcosa tra 2^n e 2^(n+1). quindi, il somma è O(2^n).

Quindi T(n) = O(2^n).