Part I: Fundamental

Problem 1 Saving the niece.

One day, your niece comes to visit you with a worried look on her face. It turns out that her teacher just gave a very tricky problem as part of their VCE Algorithmics Unit 3. She has spent 3 days working on it without any success. As a loving (and very capable) uncle/aunt, you must help her out. Here is the problem.

Consider the algorithm mystery() whose input is an integer array A of size n.

a) What does the algorithm compute? Justify your answer.

b) What is the algorithmic paradigm the algorithm belongs to?

c) Write the recurrence relation (formula + base condition) for C(n), which counts the number of array elements comparisons.

d) Solve the recurrence relation by the backward substitution method to obtain an explicit formula for C(n) in n.

e) Write the complexity class that C(n) belongs to using the Big-Θ notation.

Table 1: A toy example of five transactions with their corresponding sizes and fees.