Log In
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?

  1. $256$
  2. $512$
  3. $1024$
  4. $2018$
in Algorithms
edited by
ratio of both will be same. so in the end

x.log x=12*64*9





so x=512

4 Answers

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,
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$

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

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.

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.

1 vote

Hope this helps :)

How can one suddenly understand in exam that 4608 is equal to 512*9?

@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


Related questions

30 votes
7 answers
Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode. DOSOMETHING (c, a, n) $z \leftarrow 1$ ... , then the output of DOSOMETHING(c, a, n) is _______.
asked Feb 16, 2015 in Algorithms jothee 2.8k views
45 votes
10 answers
Let $f(n) = n$ and $g(n) = n^{(1 + \sin \: n)}$, where $n$ is a positive integer. Which of the following statements is/are correct? $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ Only I Only II Both I and II Neither I nor II
asked Feb 15, 2015 in Algorithms jothee 6k views
33 votes
4 answers
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes ______.
asked Feb 15, 2015 in Algorithms jothee 3.6k views
46 votes
4 answers
Consider the following recursive C function. void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); } If $get(6)$ function is being called in $main()$ then how many times will the $get()$ function be invoked before returning to the $main()$? $15$ $25$ $35$ $45$
asked Feb 15, 2015 in Algorithms jothee 5.7k views