Quick sort time complexity

Question

I recently read about time complexity and I found out that Quick sort has an average time complexity of O(nlog(n)).

Question 1: What I do not understand is how is the log(n) present in the time complexity equation?

Question 2: Why do we always use the big O notation to find the time complexity of algorithms? Why don't we use other notations?

Answer 1

How did the logn got into the complexity formula?

• For each step, you invoke the algorithm recursively on the first and second half.

• Thus - the total number of steps needed, is the number of times it will take to reach from n to 1 if you devide the problem by 2 each step.
  So you are actually looking for a k such that:

  n / 2 /2 / 2 / ... /2 = 1
          ^
       (k times) 
  

  But, note that the equation is actually: n / 2^k = 1. Since 2^logn = n, we get k = logn. So the number of steps (iterations) the algorithm requires is O(logn), which will make the algorithm O(nlogn) - since each iteration is O(n).

Note: The complexity in here is not exact, quicksort in rare cases decays to O(n^2), it is depends on the pivot selection. The "devide the problem by 2 each step" is a simplification, but it does not change the average analyzis of the algorithm.

Why use big O notation?
It is simple and platform independent.
The exact number of op (and sometimes even comparisons) is platform dependent. (If instruction set A is richer then instruction set B, it will probably need more ops).
It is definetly not the only method used. For real life applications, the exact run time (in seconds) is very important factor and is often used.

So, in short - big O notation gives us easy to calculate - platform independent approximation on how will the algorithm behave asymptotically (at infinity), which can divide the "family" of algorithm into subsets of their complexity, and let us compare easily between them.

Also, other notations that are used are small o, theta and big/small omega.

Answer 2

Ques 1. Quick sort's worst case time complexity is O(n^2),whereas average case complexity is O(nlogn). logn factor depends upon the pivot, how the algorithm choose it.

Quick sort worst case time complexity occur when pivot produces two regions one of size 1 element and other of size (n-1) elements recursively.Whereas average case occurs when pivot chooses two regions such that both regions produced have a size of n/2.

So recursive relation produced is T(n)=2T(n/2)+Θ(n).

                  f(n)=Θ(n)     
                  h(n)=n^log2(2)=>n 
                  since f(n) = h(n) so
                  T(n)= f(n)logn =>n(logn).

(here we are using Θ notation since worst case complexity(big O) of quick sort is O(n^2) and here we are calculating average case complexity.)

Ques 2. We use big O notation because it gives the idea of worst case time complexity which limits the algorithm even when the arguments tends infinity,that means the algo will atleast run in this time complexity and cannot go beyond it.

Whereas there are other notations such small o, theta and big/small omega which are used very often as they have limited applications.

Answer 3

Please read Introduction to Algorithms by Cormen et al. In the chapter 3 you will find a good explanation about Complexity Analysis of algorithms. You will find that Big O is not the only asymptotic notation that is used.

Answer 4

Even though this is more of a question about computer science in general which can be explained more thoroughly by the comments on the question --

Question 1: the log(n) is there to denote that the problem scales at a higher rate than a O(n) problem by a factor log(n). The terms smaller than n*log(n) (like n) are omitted because they scale slower than the largest term.

Question 2: There are other metrics, O (big O) is the worst case rate of problem expansion. See the book links in the comments to see what the others are/mean, as it's better explained there.