Write the value of the following recurrences from 0 to 4 3p

Write the value of the following recurrences from = 0 to 4. (3pts) (a)T(0) = 2 T(1) = 2 T(n) = 2n+ 2T(n2) (b)T(0) = 1 T(n) = 2T(n1) (c)T(0) = 1 T(1) = 1 T(n) = 3n 2 +n+T(n2)

Solution

(a )   Answer below

T(0) = 2

T(1) = 2

T(n) = 2T(n2)+2n               // perhaps a typographical error in T(n2)

Note: // T(n2) is not a taken as part of recurrence. In a recurrence , each recursive call to T(n) , size of n must be decreases .Here, it does not decrease the size of n. So I think n2 can be taken as T(n/2) or T(n-2). Here I take T(n2) as T(n/2).

Value of recurrence from n=0 to 4

n

T(n)

0

2

1

2

2

2T(n/2)+2n =2T(1)+2*2=8

3

Is not a proper value for the recurrence. N=3 is correct if n/3 is interpreted as floor(n/3) or ceiling(n/3)

If n/3 is taken as floor(n/3) then

2T(n/2)+2n =2T(1)+2*2=8

4

2T(n/2)+2n =2T(2)+2*4=24

(b )   Answer below

T(0) = 1
T(n) = 2T(n1)          // perhaps a typographical error in T(n1)

Note: // T(n1) is not a taken as part of recurrence. As it does not decrease the size of n. So I think T(n1) can be taken as T(n-1). We cannot take T(n/1) as it also same as T(n)

So recurrence is

T(0) = 1
T(n) = 2T(n-1)         

Value of recurrence from n=0 to 4

n

T(n)

0

1

1

2T(n-1)=2T(0)=2*1=2

2

2T(n-1)=2T(1)=2*2=4

3

2T(n-1)=2T(2)=2.4=8

4

2T(n-1)=2T(3)=2.8=16

(c )   Answer below

T(0) = 1

T(1) = 1

T(n) = 3n 2 +n+T(n2)     // Assuming typographical error

Corrected: T(n)=3n^2+n+T(n/2)

Value of recurrence from n=0 to 4

n

T(n)

0

1

1

1

2

T(n/2)+ 3n^2+n=T(1)+3*2^2+2= 1+3*2^2+2=15

3

3 is not a proper size foe n for the recurrence, SoT( n/2) can be interpreted as T(floor*n/2))

T(n/2)+ 3n^2+n=T(1)+3*3^2+3= 1+3*3^2+3=31

4

T(n/2)+ 3n^2+n=T(2)+3*4^2+4= 15+3*4^2+4=67

n	T(n)
0	2
1	2
2	2T(n/2)+2n =2T(1)+2*2=8
3	Is not a proper value for the recurrence. N=3 is correct if n/3 is interpreted as floor(n/3) or ceiling(n/3) If n/3 is taken as floor(n/3) then 2T(n/2)+2n =2T(1)+2*2=8
4	2T(n/2)+2n =2T(2)+2*4=24