x.log x=12*64*9

=6*128*9=

3*256*9=

18*256=

9*512

so x=512

37 votes

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?

- $256$
- $512$
- $1024$
- $2018$

67 votes

Best answer

The worst case time complexity of Mergesort is $k \times n \log n$ for an input of size $n$.

For an input of size $64$, the algorithm takes $30s$. Therefore,

$$\begin{align}

k \times 64 \log_2{64} &= 30s\\[1em]

k \times 384 &= 30s\\[1em]

\implies k &= 0.078125s

\end{align}$$

Let the size of the problem that can be solved in $6$ minutes be $x$. Then,

$$k \times x \log_2 x = 360s$$

From this, we get:

$$\begin{align}

x \log_2 x &= \frac{360s}{0.078125s}\\[1em]

\implies x &= 512

\end{align}$$

Correct Answer: $B$

For an input of size $64$, the algorithm takes $30s$. Therefore,

$$\begin{align}

k \times 64 \log_2{64} &= 30s\\[1em]

k \times 384 &= 30s\\[1em]

\implies k &= 0.078125s

\end{align}$$

Let the size of the problem that can be solved in $6$ minutes be $x$. Then,

$$k \times x \log_2 x = 360s$$

From this, we get:

$$\begin{align}

x \log_2 x &= \frac{360s}{0.078125s}\\[1em]

\implies x &= 512

\end{align}$$

Correct Answer: $B$

34

The complexity of mergesort is $O(n \log n)$.

The actual time taken will depend on the implementation, processor speed, and many more things. That's why we use a constant multiplicative factor along with the asymptotic complexity.

Note that we should also have used a constant additive factor, so the time should have been assumed as $k \times n \log n + c$, but the question doesn't have enough information to solve it using that. So we ignore the constant factor.

The actual time taken will depend on the implementation, processor speed, and many more things. That's why we use a constant multiplicative factor along with the asymptotic complexity.

Note that we should also have used a constant additive factor, so the time should have been assumed as $k \times n \log n + c$, but the question doesn't have enough information to solve it using that. So we ignore the constant factor.

48

@Pragy : thanks for the answer.

in the solution If we do

**(k * x log _{2}x)/(k * 64log_{2}64 ) = 360/30**

**xlog _{2}x = 12 * 64 * 6 = 2^{9} * 9 = 512 * log_{2}512**

so , x = 512. it can reduce time to solve

Note : that approach is result of solution you gave :)

1

@Praveen Saini why ae we dividing the two equations, *(k * x log2x)/(k * 64log264 ) can you please explain the logic behind it?*

21 votes

number of levels in merge sort =log_{2}n

work done at each level = n

total work done = n log_{2}n .

given n=64 or 2^{6}

n log_{2}n= 64 x 6= 384 ----->> total work done in 30 seconds .

=> work done in 6 mins = 4608

now we know the formula .. just put in the values .. n log_{2}n=4608

512 satisfies the equation = 512 x log_{2} 2^{9 }

=> 512 x 9= 4608

5 votes

You can answer a wee bit faster if u think that, were the algo linear time, then in 6 minutes u cud solve 128 * 6 = 768 problems. But since the algo complxeity takes a factor of (lg n) time more, the number of problems that can be solved will be less than 768. So, 512. Warning: this is a fairly naive approach.

1 vote

1

@Gupta731 You can't be guaranteed that the number will behave nicely when you try to manipulate it algebraically.

Hit and trial is a much better way to do it.

My mental process:

$x=1024, log_2x=10...$Too big.

$x=256,log_2x=7...$Too small.

$x=512,log_2x=9... 512×9=4608512×9=4608.$ Bingo!

Divisible by 9 is discussed below:

A number is divisible by 9, if the sum is a multiple of 9 or if the sum of its digits is divisible by 9.

**Example- 99**

Sum of the digits of 99 = 9 + 9 = 18, which is divisible by 9.

Hence, 99 is divisible by 9