Consider an ordered (sorted) array A of size n and the following ternary search algo- rithm for finding the index i 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