4b)

b) Design an algorithm in pseudocode (or any programming language of your choice) that, given any array A of n integers, returns 1 if there are A[i] and A[j] in A such that A[i]+A[j]=0; otherwise, the algorithm returns 0 . Your algorithm must not change the given array and may only use a constant amount of additional space. (4 marks) What is the time complexity of your algorithm in terms of O notation? (1 mark) Now suppose the algorithm may change the array and use any amount of additional space. Describe an algorithm for this problem (without giving any code) that would run significantly faster than your original algorithm. What is the time complexity of this algorithm? (4 marks)