835 views
3 votes
3 votes

You are  given a 1 billion numbers. The time require in seconds to sort them provided sorting thousand numbers takes 100 microseconds will be _______

  1. 10,000
  2. 512
  3. 300
  4. 65536

1 Answer

Best answer
10 votes
10 votes
1 billion $= 10^9$

Apply best Sorting algorithm,
$T(n) = O(n\lg n) = k.n\lg n$

The time require in seconds to sort them provided sorting thousand numbers takes 100 microseconds
$100 \times 10^{-6} = k \times 1000 \lg 1000 \\\implies k = \frac{10^{-7}}{\lg 1000}$

For n = 1 Billion let $x$ be the requied time.
$x = k \times 10^9 \lg 10^9 \\=  \frac{10^{-7}}{\lg 1000} 10^9 \times \lg 10^9 \\=300 s$
selected by
Answer:

Related questions

2 votes
2 votes
2 answers
1
Bikram asked Oct 4, 2016
767 views
About how many compares will Quicksort() make when sorting an array of N items that are all equal?$\Theta(\lg N)$$\Theta(N\lg N)$$\Theta(\lg \lg N)$$\Theta(N/\lg N)$
2 votes
2 votes
4 answers
2
Bikram asked Oct 4, 2016
601 views
Is an array that is sorted in decreasing order a max-heap?always yesalways nosometimes onlyyes but not in presence of duplicates