Problem 3 Let Tn be the running time of ALG1 called for l 0

Problem 3. Let T(n) be the running time of ALG1 called for l 0 and r n 1. Write the recurrence for T(n), solve it and give a big-Theta bound. ALG 1 (A,l,r) input: array ALl..r] l if T l then return 0 2 0, n r-l +1 3 for i l to r A i 5 s ALG 1 (A, i, r n/3) 6 st ALG 1 (A, l n/3, r) return

Solution

T(n)=T(n/2)+n,T(0)=T(1)=1

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

T(0)=0

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