[10 marks Consider the following idea for searching for a number x in a list S ofn mumbers in sorted order, where n is an exact multiple of 4: Look at every fourth number comparing it to x. If you find x, sop. If you ncounter a number bigger than x, then go backwards one mumber at a time in S at most three times, looking for x. Again, if you find x, stop Here is the pseudocode for this algorithm Inputs: positive integer n which is a multiple of 4, sorted array S ofn keys indexed froml to n, a key x Outputs: position, the location of x in S (0 of x is not in S) void FourthSearch( int n, const keytype S[l, keytypex, index& position) index i last boolean done; position 0 done false i-4 while (Iposition0) && (ien) && (done false )) ifx-S position else if (x>SiX ji+4 else //go backwards last i-3 while (not done) j-1 if (S)x ) position i done true; ese if (x> S) or dene true last) endwhile endelse /endwhile Do an average case analysis of this algorithm, assuming that n-4, and that all input types are equally likely and all keys in S are distinct. Count, as your basic operation comparisons of x with keys in S (and count ALL such comparisons). You should have all inputs partitioned into 9 types if you are doing this analysis correctly. You must explain your input partitions clearly.