6. Form the recurrence relation for time complexity of the following function. Explain your method. Assume...

• 
  

Transcribed Image Text:

6. Form the recurrence relation for time complexity of the following function. Explain your method. Assume that the parameter for the recurrence is the size of the array A. (10) Func(int p, int q) //pq, p, q0; p, q are indices of array A { if(p==q) return A[p]; else { if (q=p+1) return (A[p]+A[q]); else { a=p+(q-p)/3; } } b=p+(2*(q-p))/3; x=Func(p,a); y=Func(a+1,b); z=Func(b+1,q); return x+y+z; 6. Form the recurrence relation for time complexity of the following function. Explain your method. Assume that the parameter for the recurrence is the size of the array A. (10) Func(int p, int q) //pq, p, q0; p, q are indices of array A { if(p==q) return A[p]; else { if (q=p+1) return (A[p]+A[q]); else { a=p+(q-p)/3; } } b=p+(2*(q-p))/3; x=Func(p,a); y=Func(a+1,b); z=Func(b+1,q); return x+y+z;