CS381 HW2

3)
i) Assume index of arrays is from 1 to n.

Create an array, B of size n, initialized to 0;
FOR i = 1 to n
	IF B[A[i]] is nonzero
		RETURN (B[A[i]], i)
	ELSE
		SET B[A[i]] to i
	END IF
END FOR

Algorithm is O(n) because there is only 1 for loop of size n and the work being done inside the loop is constant time. The worst case happens when we find the pair at the last index


ii) Assume index of arrays is from 1 to n.

Create an array, B of size n, initialized to 0;
FOR i = 1 to n:
	increment B[A[i]];
END FOR
SET sum = 0
FOR i = 1 to n:
	IF B[i] > 1
		increment sum by B[i]*(B[i]-1)/2
	END IF
END FOR
RETURN sum

Algorithm is O(n) because there are two separate loops of size n and within both of these loops, constant time work is done.