The Gateway to Computer Science Excellence
+33 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?

  1. $256$
  2. $512$
  3. $1024$
  4. $2018$
in Algorithms by Veteran (105k points)
edited by | 4.8k views
ratio of both will be same. so in the end

x.log x=12*64*9





so x=512

3 Answers

+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,
k \times 64 \log_2{64} &= 30s\\[1em]
k \times 384 &= 30s\\[1em]
\implies k &= 0.078125s
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:
x \log_2 x &= \frac{360s}{0.078125s}\\[1em]
\implies x &= 512

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

@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 :) 

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

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


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

Nice explanation sir got it completely!

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

@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

Thank you, Ayush
+21 votes

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)
+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.
by (205 points)

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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,616 answers
102,352 users