Homework 18

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

## Reviews

There are no reviews yet.