Consider an ordered linked list with n entries in ascending order. Each entry has 2 components: a key component of type int and the usual next link component.

a) Write a function to insert a new entry with key x into its proper place. Note that a key may be added as the new first or last entry in the list, and so there are n+1 locations where x could be inserted.

b) Assume that each of the n+1 possibilities is equally likely. Determine the average number of times ints are compared in the above insertion algorithm. Your answer should be a precise function of n. An asymptotic answer (such as one that uses big-oh, big-theta, etc.) is not acceptable.

Language: C or C++