Computing Recurrence equation (Algorithms Analysis)

Question

I want to know how to solve this question by iterative method

Answer 1

Since you should do your homework yourself, I'll show you the solution for

• T(1)=1
• T(n)=2T(n/2)+n
• for n=8

n = 8
T(n) = T(8)
= 2T(8/2)+8
= 2T(4)+8
= 2*(2T(4/2)+4)+8
= 2*(2T(2)+4)+8
= 4T(2)+8+8
= 4T(2)+16
= 4*(2T(2/2)+2)+16
= 4*(2T(1)+2)+16
= 8T(1)+4+16
= 8T(1)+20
= 8*1+20
= 28