Wie löst ich die rekursive Komplexität für t (n) = t (n/2) + 2^n mit Iterationsmethode?

Question

Ich versuche die obere und untere Grenze zu finden, die wahrscheinlich o (2^n) ist

T (n) = 1 für n <= 4

Ich weiß, dass das allgemeine Organ ist:

T (n) = t (n/2^(i + 1)) + sum von i = 0 bis k von 2^(n/2^i)

---

Von hier aus weiß ich nicht, wie ich vorgehen soll.

Answer 1

Es gibt ein Problem mit Ihrer Notation. Das allgemeine Organ sollte sein:

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

Nach diesem Schritt lassen wir uns i = log(2, n) - 1, so dass T(n/2^(i+1)) = T(1).

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

Beachten Sie, dass sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) ist 2^n + 2^(n/2) + 2^(n/4) + ..., was kleiner als 2^n + 2^(n-1) + 2^(n-2) + .... Das letztere Zeug ist jedoch 2^(n+1) - 1. Das frühere Zeug ist also etwas dazwischen 2^n und 2^(n+1). deshalb, die Summe ist O(2^n).

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