# Big O(n log n) and Quicksort number of operations

I have an Array with `1,000,000` unsorted elements. I need to calculate expected number of operations that needs to be performed to sort array using `Quicksort` algorithm in common situations (not the n^2 worst case).

I am not sure how `(n log n)` is calculated - does it even makes sense to calculate this?

If `(n log n)` = `(n*log(some base)n)` what base would be for `Quicksort`?

• do you know how to implement quicksort? – jk. Jun 19 '12 at 8:57
• @Dusan: do you know that changing the base of a logarithm just means multiplying it by a constant? – Doc Brown Jun 19 '12 at 11:34
• @Doc: Yes, by previous answers, now all of it makes sense in the context of big O and why the base is relevant. However, in some situations like Binary Search which is O(Log N) you need to work with base of 2 and you can calculate how many steps you need to take to locate element (for 1,000,000 is 20). If I would use base 10 in this case it would make no sense at all. I initially taught that I can calculate number of steps for Quick Sort based on it's big O notation like I can for Binary Search and some other stuff. I was sonfused about big O notation and meaning. – Dusan Jun 19 '12 at 12:12
• To get an exact constant factor (for random order?), you will need to average over all possible partitions of the array. You will also need to choose an arbitrary weight for the expense of a recursive function call vs. a compare-and-swap operation. – comingstorm Jun 19 '12 at 21:53

Before you go on and continue your maths, I would recommend trying to understand big O notation. The notation helps you to have an idea about the evolution of computation costs when input size changes. The base of the log is irrelevant here as it just affects the constant factor

If you need to provide a precise number of operations, you have to analyse the algorithm and the data structure used for its implementation, and not just use a formula.

• I thought so, that is why I was asking if it makes sense to calculate anything here. I am aware that the O(n log n) illustrates the algorithm cost in relation to n. Thanks! – Dusan Jun 19 '12 at 9:15

The article on quicksort on Wikipedia explains what the algorithm is.

It shows an animation of how the sorting is being performed.

The base is '2'.

• +1, Thanks for the link, the animation is great, I wish I had this kind of illustration in the old days! – NoChance Jun 19 '12 at 9:25
• The base is irrelevant - 2 is as good as 10 or 42. – Doc Brown Jun 19 '12 at 11:36

the log here is in base 2, the big O notation merely says, that if you increase the value of number of elements, that is n in this case, how would the time to compute the output depend on it.

• Yes, and it is correct for big numbers only, i.e. if the calculated number of operations would be `a*x^2 + b*x + c` for a given algorithm, the big O notation would only consider the highest power: `O(n^2)` in this case. – Olivier Jacot-Descombes Jun 19 '12 at 14:55
• Yes @OlivierJacot-Descombes : I totally agree with it, I might have considered it too obvious in my answer, sorry for the mistake – potato man Jun 19 '12 at 15:30