GATE Overflow | Algorithms | Test 1 | Question: 13

Question

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

• A. 10,000
• B. 512
• C. 300
• D. 65536

Comments

afer this step how to proceed?

Answer 1

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$

Comments

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?