1. (a) A mathematical property P is an invariant for the code fragment Code, if the Triple: {p} Code {P} is true. Which of the following instances are true and which are false? In each case give values for the variables to support your answer. Property P Code Property P Code XX+1 X+YKK YEY+1 YEY- 2 X +1 X + Y is even X X + Y is odd XX+1 YEY+2 Y is even XX+1 YY+X X+Y=k XX+1 YEY-1 X + Y is even XX+1 YY +2 [15 marks) (b) Let (n) and g(n) be functions over the natural numbers. Explain what the following means: 1. g(n) is in f(n)) II. An algorithm is in the complexity class e(/(n)). [10 marks) (c) The following is an incomplete algorithm that inputs an array, and decides if the elements are sorted in ascending order. Input: Array Al...] Output: true if sorted in ascending order, false otherwise 1 SORTED ? 2 for it to ? do 3 if A[i]> A[i+1] then SORTED false s return SORTED i. Complete the above algorithm by replacing?' in lines 1 and 2, SO that it satisfies the specification. [8 marks] II. What is the complexity of this algorithm in e notation? (2 marks] ill. How many times is line 3 executed in the best case? (2 marks] iv. Modify the algorithm to improve its best case performance. Give an example array which will demonstrate the improvement. [13 marks]