Skip to content

Latest commit

 

History

History
29 lines (15 loc) · 1.62 KB

p5.md

File metadata and controls

29 lines (15 loc) · 1.62 KB

Problem

Solve the recurrence T(n)=2T(n/2)+n-1 where n=2^k is assumed; assume that T(n) is constant if n<=2.

Solution

T(n)=(n-1)+2T(n/2)

=(n-1)+2((n/2-1)+2T(n/4))

=(n-1)+(n-2)+4T(n/4)

=(n-1)+(n-2)+4((n/4-1)+2T(n/8))

=(n-1)+(n-2)+(n-4)+8T(n/8)

=(n-1)+(n-2)+(n-4)+…+(n-2^(k-2))+2^(k-1)T(2)

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

=(log(n-1))n–n/2+n/2T(2)+1

let T(2) be a constant C.

=nlog_2n+(c-3)n/2+1