462 views

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 comment

afer this step how to proceed?

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$

Sir, Why is the log base taken as 10?
^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) ..

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