Description
The algorithm below is a reduction that uses the solution to the Bandersnatch (BS) problem to solve the JubJub (JJ) problem. You may assume that
this reduction is correct.
Input: data: array of positive integers
Input: n: size of data
Output: JubJub(data)
1 Algorithm: JubJubReduction
2 cap = max(data)
3 for i = 1 to n do
4 x = min(data)
5 if x > cap then
6 return false
7 end
8 Bandersnatch(data)
9 end
10 return true
Suppose we know that BS has a worst-case complexity that is bounded
above by O(B(n)) and below by Ω(b(n)), while the worst-case complexity of JJ
is known to be O(J(n)) and Ω(j(n)), where B(n), b(n), J(n), and j(n) are all
Ω(n
10). Answer the following questions about the JubJubReduction algorithm.
1. What is the worst-case time complexity of JubJubReduction?
2. Which of the following four statements must be true based on JubJubReduction? Please justify your answer.
(a) BS is O(J(n)/n).
(b) BS is Ω(j(n)/n).
(c) JJ is O(nB(n)).
(d) JJ is Ω(nb(n)).
1