edited by
19,930 views
59 votes
59 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$
edited by

5 Answers

Best answer
99 votes
99 votes
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 by
28 votes
28 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
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.
4 votes
4 votes

 

Time complexity of merge sort = O(n log n) = cn log n
where c is some constant
It is given that for n = 64,
cn log n = 30
c × 64 log 64 = 30
c × 64 × 6 = 30
c = 5/64
Now, the value of n for
c n log n = 360
5/64 × n log n = 360
n log n = 360×64/5
= 72 × 64 = 29 × 9
So for n = 29, it satisfies.
So, n = 29 = 512

Answer:

Related questions

67 votes
67 votes
11 answers
2
go_editor asked Feb 15, 2015
17,262 views
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))$On...
44 votes
44 votes
5 answers
3
go_editor asked Feb 15, 2015
10,735 views
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 i...
60 votes
60 votes
5 answers
4