Hard recurrence relation Q

Gary

2010-02-06 5:42 am

Evaluate the following recurrence relation.

T(n) = T(n/2) + nb logn
where T(1)=1

Please provide a detailed solution. Thx.

更新1:

same as T(n) = T(n/2) + b x n x logn where T(1)=1

回答 (1)

mathmanliu

2010-02-06 10:43 am

✔ 最佳答案

T(2^n)=T[2^(n-1)] + b*2^n*nlog2
Set A(n)=T(2^n), then A(n)=A(n-1)+ blog2*n*2^n, A(0)=T(1)=1
A(n)=A(n-1)+b log2* n*2^n
A(n-1)=A(n-2)+b log2*(n-1)*2^(n-1)
....
A(1)=A(0)+ b log2* 1*2
A(0)=1
so, A(n)= 1+b log2*[1*2+ 2*2^2+3*3^3 + ...+n*2^n] -----(***)
Let S=1*2+2*2^2+3*2^3+...+n*2^n, then
2S= 1*2^2+2*2^3+...+(n-1)*2^n+ n*2^(n+1)
so, S= n*2^(n+1) -[ 2+2^2+...+2^n]= n*2^(n+1)- 2(2^n -1)=(2n-2)*2^n + 2
Put S into (***), then T(2^n)=A(n)=1+ b log2*[(2n-2)*2^n + 2]
so, T(n)=1+ b log2*{ [2log_2 (n) -2]*n + 2}= 1+ b{ [2log(n)-log(4)] n + log(4) }

👍 0 👎 0