CODEWITHSUNDEEP
timequicksort
George
George

Reputation: 194

Time performance of QuickSort

QuickSort algorithm sorts 10.000.000 numbers. The running time was 5.3 seconds. I am wondering what is the running time if there were 1.000.000.000 numbers.

Is it logical to take about 681 seconds?

(It is a hypothetical question, so we don't depend on the computer's RAM or CPU perfomance.)

Upvotes: 0

Views: 149

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

The runtime of quicksort is, on average, O(n log n). Let's suppose that the runtime has the form c n log n for some constant c. You know that the runtime for n = 10,000,000 is 5.3s, so we get

10,000,000 c log 10,000,000 = 5.3s

10,000,000 c · 7 = 5.3s

c = 75.71ns

So now let's plug in n = 1,000,000,000:

c n log n =

75.71ns · 1,000,000,000 · log 1,000,000,000

= 681.43s

So yes, your estimate is reasonable.

Upvotes: 2

Baronz
Baronz

Reputation: 677

Wikipedia page on Quicksort: https://en.wikipedia.org/wiki/Quicksort

StackOverflow on Worst Case: Worst case for QuickSort - when can it occur?

Here it is answered on the math forum for complexity: https://math.stackexchange.com/questions/96767/worst-case-complexity-of-the-quicksort-algorithm

Here is an answer about the time: https://math.stackexchange.com/questions/1071229/expected-time-of-quicksort?rq=1

Upvotes: 0

Related Questions