You are executing Linear $($Sequential$)$ Search algorithm on an array of size n$.$ Suppose

that the key you are searching for is included in the array. Also you know that the probability of

finding the key at the last position of the array is $1/3,$ and the probability of finding the key at

the second last position is $1/3$ as well. Furthermore, the probability of finding the key at every

other positions are all equal to each other. Answer the following three questions.

a$)(6$ pts$)$ What is the probability $($as a function of n$)$ of finding the key at any position between

the first and the third last array positions?

b$)(8$ pts$)$ What is the average case complexity function $()$ for Linear Search under the

above conditions? Suppose that a comparison as the basic operation.

c$)(6$ pts$)$ If your current computer can execute one basic operation in $6$ nsec$,$ what would be

the expected average running time on an array of size $20?$

$(20pts$ You are executing Linear $($Sequential$)$ Search algorithm on an array of size $n.$ Suppose

that the key you are searching for is included in the array. Also you know that the probability of

finding the key at the last position of the array is $\frac{1}{3},$ and the probability of finding the key at

the second last position is $\frac{1}{3}$ as well. Furthermore, the probability of finding the key at every

other positions are all equal to each other. Answer the following three questions.

a$)(6$ pts$)$ What is the probability $($as a function of $n)$ of finding the key at any position between

the first and the third last array positions?

b$)(8$ pts$)$ What is the average case complexity function $T_A(n)$ for Linear Search under the

above conditions? Suppose that a comparison as the basic operation.

c$)(6$ pts$)$ If your current computer can execute one basic operation in $6nsec,$ what would be

the expected average running time on an array of size $20?$