in Algorithms
462 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
in Algorithms
by
462 views

1 comment

afer this step how to proceed?

0
0

1 Answer

10 votes
10 votes
Best answer
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

4 Comments

Sir, Why is the log base taken as 10?
0
0
^here in case of sorting, base of Log is handled by that constant part k.
you can assume any valid base here.. ans would be same .. work on maths and understand the proof of time complexity O(nlong n) ..
0
0

@Digvijay Pandey sir, why not O(nlogn)=knlogn + c? how c assumed as zero?

0
0
Answer:

Related questions