FindProduct Input: a1, a2,...,an n, the length of the sequence. prod, a target p
ID: 3011218 • Letter: F
Question
FindProduct
Input: a1, 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
For j = i+1 to n
If (ai·aj = 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.
Explanation / Answer
(a) For the given algorithm, if condition will execute the most number of times till the ai * aj = Prod condition satisfies for the last two numbers in the series 1, 2, ... n. i.e. (n-1) * n. Or it will also executes till the end even if the condition does not satisfy for any of the prod value.
In short it will execute till (n-1)*n
(b) Omega(n^2)
(c) Yes it was important to use the worst-case input for the lower bound. There are inputs which will result into complexity of omega(1). This does not give the actual worst case scenario.
(d) upper bound notation O(n^2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.