x.log x=12*64*9

=6*128*9=

3*256*9=

18*256=

9*512

so x=512

The Gateway to Computer Science Excellence

+61 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$

+29

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.

+41

@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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,616 answers

195,897 comments

102,352 users