Discrete Mathematics

PLZ do not just copy and paste other's work.

Exercise 7.3.4: Worst-case time complexity - finding a target product of two numbers. About Find Product Input: a4, a2....,an n, the length of the sequence. prod, a target product. Output: "Yes" if there are two numbers in the sequence whose product equals the input "prod". Otherwise, "No". For i = 1 to n-1 For j = 1+1 to n If (a'a; = prod), Return( "Yes") End-for End-for Return("No") (a) Characterize the input that will cause the "if" statement in the inner loop to execute the most number of times. (b) Give an asymptotic lower bound for the running time of the algorithm based on your answer to the previous question. c) Was it important to use the worst-case input for the lower bound? That is, would any input of a given length have resulted in the same asymptotic lower bound? (d) Give an upper bound (using O-notation) for the time complexity of the algorithm that matches your asymptotic lower bound for the algorithm