2 Write the value of the following recurrences for n 1 2 4

2. Write the value of the following recurrences for n = 1, 2, 4 and 8. (3pts)
(a) T(1) = 2 T(n) = 5T(n/2)
(b) T(1) = 2 T(n) = n + T(n/2)
(c) T(1) = 0 T(n) = n2 + n + T(n/2)

Solution

(a) T(1) = 2 T(n) = 5T(n/2)

n=1 ; T(1) = 2

n=2; T(2) = 5T(2/2) = 5T(1) = 5*2 = 10

n=4; T(4) = 5T(4/2) = 5T(2) = 5*10 = 50

n=8; T(8) = 5T(8/2) = 5T(4) = 5*50 = 250

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

n=1 ; T(1) = 2

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

n=4; T(4) = 4+T(4/2) = 4+T(2) = 4+4=8

n=8; T(8) = 8+T(8/2) = 8+T(4) = 8+8 =16

(c) T(1) = 0 T(n) = n2 + n + T(n/2)

n=1 ; T(1) = 0

n=2; T(2) = 2² + 2 +T(2/2) = 4+2+T(1) = 6+0=6

n=4; T(4) = 4² + 4 +T(4/2) = 16+4+T(2) = 20+6 = 26

n=8; T(8) = 8² + 8 + T(8/2) = 64+8+T(4) = 72+26 =98