3. (30 points) Consider an ordered (sorted) array A of size n and the following ternary search algorithm for finding the index such that A[i] = K. Divide the array into three parts. If A[n/3] > K, the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last third of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3] = K, or return 2n/3 if A[2n/3]=K. (a) Write the recurrence relation for the number of comparisons C(n) in the average case for the binary and ternary searches and solve the ternary average case only. (b) Do the following experiment (need to write a program in the language of your choice): (i) Generate arrays of sizes n = 500, 1000, 2000, 4000 and 8000. Fill the arrays as follows: A[i] = integer(8 i); i=0,1,2, ..., n-1.