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, 2012 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, 2012 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, 2012 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. Jun 19, 2012 at 21:53
  • For computer science, It is normally 2.Base 2 logarithms tell us how many times we can split into halves. if we write log n we mean log2 n
    – AjayGohil
    Sep 28, 2020 at 7:12

3 Answers 3


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, 2012 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, 2012 at 9:25
  • 1
    The base is irrelevant - 2 is as good as 10 or 42.
    – Doc Brown
    Jun 19, 2012 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. Jun 19, 2012 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, 2012 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.