Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
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'.

share|improve this answer
    
+1, Thanks for the link, the animation is great, I wish I had this kind of illustration in the old days! –  Emmad Kareem Jun 19 '12 at 9:25
1  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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