$($a$)3$ marks$)$ What is the running time of interpolation search on A $=[1,2,..,$n$-1,$ n$1000]$ if we are searching for n$-1?$ Justify your answer.

$($b$)14$ marks$/$ Suppose A is an array of size $16$ and Ali$]=$ tV i for $0<=$ i $<=15$ where t is some positive number. If we are searching for t in A using interpolation search, in how many iterations does the algorithm termi$-$nate? Compare the running time of this search with the average case $($for evenly spaced data$)$ running time of interpolation search. Justify your answer and explain the difference.