Correct : a

Mergesort Time Complexity:
• The worst-case time complexity of Mergesort is Θ(n log n).
• This means that the running time T(n) can be expressed as T(n) = c · n log₂ n, where c is a constant and n is the input size.

Calculate the Constant 'c':
We are given that T(64) = 30 seconds.
• Substitute n = 64 into the formula:
    T(64) = c · 64 log₂ 64
• We know that log₂ 64 = 6 (since 2⁶ = 64).
    30 = c · 64 · 6
    30 = c · 384
• Solve for c:
    c = 30 / 384

Convert Target Time to Seconds:
The new time limit is 6 minutes.
• 6 minutes = 6 · 60 seconds = 360 seconds.

Set Up Equation for New Input Size:
Let n_new be the maximum input size we can solve in 360 seconds.
• T(n_new) = c · n_new log₂ n_new
• Substitute the values for T(n_new) and c:
    360 = (30 / 384) · n_new log₂ n_new

Solve for n_new log₂ n_new:
• Multiply both sides by 384/30:
    360 · (384 / 30) = n_new log₂ n_new
• Simplify the left side:
    (360 / 30) · 384 = n_new log₂ n_new
    12 · 384 = n_new log₂ n_new
    4608 = n_new log₂ n_new

Check the Given Options:
We need to find an n_new such that n_new log₂ n_new is approximately 4608.
• For n = 256:
    256 log₂ 256 = 256 · 8 = 2048
• For n = 512:
    512 log₂ 512 = 512 · 9 = 4608
• For n = 1024:
    1024 log₂ 1024 = 1024 · 10 = 10240
• For n = 2048:
    2048 log₂ 2048 = 2048 · 11 = 22528

Comparing the calculated values with 4608, n = 512 yields an exact match.
Therefore, the maximum input size that can be solved in 6 minutes is 512.