# GATE2015-3-27

6.2k 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
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$

edited
4
here why are v considering  'k' ?? Cant v solve the problem without taking 'k' ?
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.
48

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

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

21

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

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

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

0
How can one suddenly understand in exam that 4608 is equal to 512*9?
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

## Related questions

1
2.8k views
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 _______.
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
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 ______.
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$