Question: a) Explain how the average-case computational complexity of an algorithm, with finitely many possible input values, can be interpreted as an expected value.
b) What is the average-case computational complexity of the linear search algorithm, if the probability that the element for which we search is in the list is 1/3, and it is equally likely that this element is any of the n elements in the list?