Made easy workbook

Question

Assume that merge sort 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

Answer 1

merge sort algorithm time complexity is $\boldsymbol{O( n log n)}$ in all cases.

in first case ,for given input size 64 it is taking 30 secons , so $\boldsymbol{( n log _2n)}$. $C_1$=30 seconds

  64 $log_2$ 64 $C_1$ =30 seconds

$C_1$ =$\frac{30}{64*6}$

for 6 minute ,input size will be-  $\boldsymbol{( n log _2n)}$ $C_1$=6*60 seconds

 $\boldsymbol{( n log _2n)}$=$ \frac {360} { C_1}$ ,put the value of  $C_1$

    $\boldsymbol{( n log _2n)}$=$ \frac {360} {\frac{30}{64*6}}$

$\boldsymbol{( n log _2n)}$= 4608

$\boldsymbol{( n log _2n)}$=$\boldsymbol{( 512 log _2512)}$

we can compare both side and $\boldsymbol n=512$.