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)
.