Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

The worst-case running time of mergesort on an input of size $n$ is given by:

For $n = 64$:

The maximum time available is $6\text{ minutes} = 360\text{ seconds}$. We need to find $n$ such that:

Let us check the given options:

• For $n = 512 = 2^9$:

  $$n \log_2 n = 512 \times 9 = 4608$$

Thus, $n = 512$ solves the problem in exactly $6$ minutes.

Hence, (B) is the correct option.