For each problem below, state the largest theoretical lower bound that you can think of and justify. Provide

justification for this lower bound. You do not need to find an algorithm that satisfies this lower bound.

Example: Given an array of size n and a target t$,$ determine the index of t in the array.

Example Solution: $($n$),$ because in the worst case any algorithm must look through all n numbers to verify

that the target is not one of them, taking $($n$)$ time.

a$)$ Given an array of n numbers, find the second largest number.

b$)$ Given an array of n numbers, check to see if there are any duplicates.

c$)$ Given an array of n integers $($with n $>=2),$ check to see if there is a pair of elements that add to be an

even number.

$2$