Consider the following problem: You are given a number n and an array A of n numbers, indexed from 1 to n. Design an algorithm that decides if A contains the numbers 1, 2, 3,..., n, arranged in any order. For example, suppose that n=5, and A = [4, 1, 5, 2, 3], then the answer would be yes, but if A= [1, 2, 3, 4, 10] the answer would be no. Remember that you will be marked on the clarity and time efficiency of your algorithm.

a) [9 marks] Describe the main ideas of your algorithm in words, then describe your algorithm in pseudocode (try to use pseudocode which is similar to that in the textbook).

b) [4 marks] Do a worst case analysis of your algorithm, counting both the comparison of the numbers in A with anything, AND counting the number of times you write a number to an array. Use n as your input size. Be sure to explain your analysis.