Geek Answers Handbook

Solution T (n) = 2T (n / 2) + log n

I am trying to solve T (n) = 2T (n / 2) + log n

substituted n = 2 ^ k

T(2^k) = 2T(2^(k-1)) + k  
T(2^k) = 2^2 T(2^(k-1)) + 2(k-1) + k

after k steps
T(2^k) = 2^k T(1) + 2^(k-1) + 2 * (2^(k-2)) +....+k

So, basically I need to summarize the term i * 2 ^ i, where i = 1, log n - 1.
And I could not find a simple way to summarize these conditions. Am I doing something wrong? Is there any other way to solve this recursion? Will she work on her? if so, how?

Thank.

+5
source share
2 answers

first you must define a recursive export, for example T (1) then: since T (2 ^ k) = 2T (2 ^ (k-1)) + k; * we define g (k) = T (2 ^ k) / 2 ^ k; then * come to: g (k) = g (k-1) + k / 2 ^ k = g (1) + sum (i / 2 ^ i); i = 2,3,4 ... k where g (1) = T (1) / 2 = c;

it = y; y/2; y-y/2 - , .

, sum = 3/2 - (k + 2)/2 ^ k;

T (n) = 2 ^ k * g (k) = (3/2 + c) * n - (2 + logn)

+2

Wolfram | Alpha :

recurrence

solution

c_1, .

, log (n)/log (2) = lg (n), lg - .

+2

More articles:


All Articles