4.8k views

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?

1. $256$
2. $512$
3. $1024$
4. $2018$

edited | 4.8k views
0
ratio of both will be same. so in the end

x.log x=12*64*9

=6*128*9=

3*256*9=

18*256=

9*512

so x=512

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$
by Boss (22.8k points)
edited
+4
here why are v considering  'k' ?? Cant v solve the problem without taking 'k' ?
+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.
+41

@Pragy : thanks for the answer.

in the solution If we do

(k * x log2x)/(k * 64log264 ) = 360/30

xlog2x = 12 * 64 * 6 = 29 * 9 = 512 * log2512

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

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

+2
Indeed. :)
+2
thank u for answers.. i got it completely...
+3

if (x lg x)=4608 , then how to calculate value of x ?

+20

xlogx = 4608 = 512 x 9 = 512log29 = 512log512
x=512

+1
Nice explanation sir got it completely!
+1

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

+1
@Iarnav-if two things are in direct proportion(a and c are in direct proportion and say k is a constant) then

$a=kc$ implies

$\frac{a}{c}=k$
0
Thank you, Ayush

number of levels in merge sort =log2n

work done at each level = n

total work done = n log2n .

given n=64 or 26

n log2n= 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 log2n=4608

512 satisfies the equation = 512  x log2 29

=> 512 x 9= 4608

by Active (2.1k points)
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.
by (205 points)
0

I am thinking of same approach but tell me one thing algo takes logn factor more right, then how could u say that -think solution is less than 768 ? Explain this plz.