Assume that a mergesort algorithm in the worst case takes 30 seconds for an…

Idea: Assume mergesort runtime is proportional to n log2 n, so time = c · n · log2 n for some constant c.

Find c from the given data: for n = 64, time = 30 s and log2 64 = 6, so

c = 30 / (64 * 6) = 30 / 384 = 0.078125.

Target time is 6 minutes = 360 s. Solve c · n · log2 n = 360, so

n · log2 n = 360 / c = 360 / 0.078125 = 4608.

• 256 → 256 * log2 256 = 256 * 8 = 2048 (too small)

• 512 → 512 * log2 512 = 512 * 9 = 4608 (matches target)

• 1024 → 1024 * log2 1024 = 1024 * 10 = 10240 (too large)

• 2048 → 2048 * log2 2048 = 2048 * 11 = 22528 (too large)

Conclusion: 512 is the largest input size among the choices that fits within 6 minutes.