Suppose that a is a sorted (in increasing order) array of n distinct positive integers a[0]a[n1] where n is a multiple of 4 . Given a positive integer x and the array a, an algorithm S finds, by comparing values, the index of x in the array. If x is not in a the algorithm S returns 1. S can be modelled by the following decision tree: Suppose that a is a sorted (in increasing order) array of n distinct positive integers a[0]a[n1] where n is a multiple of 4 . Given a positive integer x and the array a1 an algorithm S finds, by comparing values, the index of x in the array. If x is not in a the algorithm S returns 1. S can be modelled by the following decision tree: (a) For n=12 what is the worst case number of key comparisons performed by S ? [ 2 marks] (b) Give a general expression for W(n), the worst case performance (with respect to comparisons) of S. You may assume here and in part (c) below that only one key comparison is required to determine whether xa[i]. [4 marks] (c) Suppose that, if x is in the array, it is equally likely to be in any position. Derive an expression for As(n), the average case performance for a successful search. [14 marks] Suppose that a is a sorted (in increasing order) array of n distinct positive integers a[0]a[n1] where n is a multiple of 4 . Given a positive integer x and the array a, an algorithm S finds, by comparing values, the index of x in the array. If x is not in a the algorithm S returns 1. S can be modelled by the following decision tree: (a) For n=12 what is the worst case number of key comparisons performed by S ? [2 marks] (b) Give a general expression for W(n), the worst case performance (with respect to comparisons) of S. You may assume here and in part (c) below that only one key comparison is required to determine whether xa[1]. [4 marks] (c) Suppose that, if x is in the array, it is equally likely to be in any position. Derive an expression for As(n), the average case performance for a successful search. [14 marks]