Description

N.B. If your algorithm runs in O(n)-time, then you will receive at most 10% credit.
Guidelines: Please state any assumption you make. No such assumption should contradict with what the assumptions in the question says. For instance, if you want the array index to start from 0 to n− 1, please state it. But by default as per the question, the index is 1, . . . , n. Your answer must clearly explain the algorithm properly with a justification why the algorithm is correct. Additionally, your answer must give a clear explanation of your claimed running time. Missing explanations etc will deduct marks.
1