Proving Quicksort has a worst case of O(n²)

Question

I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;



public class QuickSort 
{
    static int pivotversion;
    static int datacomparison=0;
    static int datamovement=0;

    public static void main(String args[])
    {
        Vector<Integer> container = new Vector<Integer>();

        String userinput = "data2.txt";
        Scanner myScanner = new Scanner("foo"); // variable used to read file
        Scanner scan = new Scanner(System.in);


        System.out.println("Enter 1 to set pivot to be first element");
        System.out.println("Enter 2 to set pivot to be median of first , middle , last element of the list");
        System.out.println("Your choice : ");
        //pivotversion = scan.nextInt();


        try
        {

            File inputfile = new File("C:\\Users\\8382c\\workspace\\AdvanceAlgorithmA3_Quicksort\\src\\" + userinput);
             myScanner = new Scanner(inputfile);

        }
        catch(FileNotFoundException e)
        {
            System.out.println("File cant be found");
        }


         String line = myScanner.nextLine(); //read 1st line which contains the number of numbers to be sorted

         while(myScanner.hasNext())
         {
             container.add(myScanner.nextInt());
         }


        System.out.println(line);



        quickSort(container,0,container.size()-1);

        for (int i =0;i<container.size();i++)
        {
            System.out.println(container.get(i));
        }

        System.out.println("=========================");
        System.out.println(datamovement);
        System.out.println(datacomparison);





    }


    public static int partition(Vector<Integer> container, int left, int right)
    {
          int i = left, j = right;
          int tmp;

          int pivot= 0 ;
          pivot = container.get(left);

          boolean maxarraybound = false;




          i++;

          while (i <= j) 
          {
                while ( container.get(i) < pivot && maxarraybound == false)
                {
                      if ( i == container.size()-1 )
                      {
                          maxarraybound = true;
                      }
                      else
                      {
                          i++;
                          datacomparison++;
                      }
                }
                while ( container.get(j) > pivot)
                {
                      j--;
                      datacomparison++;
                }
                if (i <= j) 
                {
                      tmp =  container.get(i);// considered data movement??

                      container.set(i, container.get(j));
                      datamovement++;

                      container.set(j, tmp);
                      datamovement++;

                      i++;
                      j--;
                }
          };

          tmp = container.get(left);

          container.set(left, container.get(i-1));
          datamovement++;


          container.set(i-1, tmp);
          datamovement++;


          return i-1;





    }

    public static void quickSort(Vector<Integer> container, int left, int right) 
    {
          int index = partition(container, left, right);
          if (left < index - 1)
                quickSort(container, left, index - 1);
          if (index+1 < right)
                quickSort(container, index+1, right);



    }


}

I am trying to prove to myself that the worst-case running time of QuickSort is indeed $O(n^2)$ by summing up the total number of data comparisons and data movements in the algorithm.

In my current situtation, I have an input of 10000 numbers.

I would expect a total sum of data comparison and data movement to be around 100 million.

I am only getting a total sum of data comparsion and data movement of around 26 million.

I am sure I have miss out some "data movement" and "data comparsion" in my algorithm, can someone point out to me where as I have no clue?

Answer 1

Asymptotic bounds don't so much tell you how long to expect an algorithm to take, or how many operations it might perform, on a fixed input. Rather, the goal is to characterize how the time taken (or operations performed) by the algorithm grows for inputs of sufficient size. What $O(n^2)$ means is that the worst-case is bounded by some function that increases quadratically; that is, if you give your algorithm a worst-case input of size $n$ and then a worst-case input of size $2n$, you should expect your algorithm to take four times as long on the larger input (since $\frac{(2n)^2}{n^2} = \frac{4n^2}{n^2} = 4$) You might try a worst-case list of around 20,000 numbers and expect to see around 104 million operations.

Why do asymptotic notations work this way? Well, mathematics aside, it's useful for understanding how programs work. Different computers can execute at different clock frequencies, so absolute time measurements wouldn't be helpful for evaluating algorithms cross-platform (unless some reference architecture was used, which is also done, but bear with me). Code compiled for different architectures may perform more or fewer elementary operations, so an exact count of operations isn't really very useful in practice. Asymptotic growth, however, which tells you how an algorithm scales, and what to expect by way of comparison when you change the input size, is a pretty reliable indicator of how programs actually scale on any given system. You could compile your Quicksort for my x86, my friend's AMD64, my dad's ARM, and my grandpa's MIPS and you'd be able to observe the expected scaling behavior. Good luck getting the same number of operations for the same algorithm and input across those platforms!

Answer 2

Your question demonstrates some confusion regarding what asymptotic notations such as $O(n^2)$ and expressions such as “worst case” mean. I recommend reading the definitions and some examples. If you have a textbook, work through its exercises. Browse through our questions as well. Understanding comes from experience, so whatever you do, do work out some cases for yourself.

Asymptotic behavior

In my current situtation, I have an input of 10000 numbers.

I would expect a total sum of data comparison and data movement to be around 100 million.

I am only getting a total sum of data comparsion and data movement of around 26 million.

Asymptotic notation such as big oh counts up to a multiplicative factor. When we say that a running time is e.g. $\Theta(n^2)$, it doesn't mean that the running time is $n^2$ — that would lack a unit (is it $n^2$ clock cycles? $n^2$ seconds? …). It means that there is a multiplicative constant $C$ (which you can think of as a unit of measurement) such that the running time is about $C \, n^2$. (Furthermore, this is the case only for large enough $n$, but here the data size is large enough.)

With a single point of measurement, you can't tell anything. Asymptotic notations don't give a value, they give a shape. If the running time of an algorithm is $\Theta(n^2)$, then for large enough $n$, if you plot the running time against the data size, the shape is (approximately) a parabola. This parabola could be at any scale. When you get a number of operations $T(n) \approx 26 \times 10^6$ for an input size $n = 10,000$, if it is indeed the case that $T(n) \in \Theta(n^2)$ and the input size is into the “asymptotic zone”, this tells you that the constant $C$ such that $T(n) \approx C \, n^2$ satisfies $26 \times 10^6 \approx C \times (10^4)^2$. Note that the constant $C$ has a unit: it's a number of elementary operations.

If you want to test experimentally whether the running time is indeed $\Theta(n^2)$, you need to test with multiple input data sizes. Calculate the constant $C$ for each data size; if the hypothesis of $\Theta(n)$ behavior is correct, then you should get approximately the same value for large enough inputs. In other words, plot the running time against the data size, and check whether the shape does look like the expected parabola.

Worst case vs upper bound

The notation $T(n) \in O(n^2)$ means that $T(n)$ is at most $n^2$, up to a scaling factor (multiplicative constant), for large $n$. The big oh gives an upper bound; it's possible that the function is in fact less than this upper bound (i.e. the upper bound is not optimal). For example, $n \in O(n^2)$ (because for all $n \ge 1$, $n \le 1 \times n^2$). The time complexity of quicksort is $O(n^2)$; it's also $O(n^3)$ and $o(42^n)$, but those statements are weaker and thus less useful.

The worst case of quicksort is $O(n^2)$ (and also $O(n^3)$, etc.). It is true that for most choices of pivot, the worst case is $\Theta(n^2)$. What this means, using $T(V)$ to denote the number of operations for the input $A$, is that
    there exists $N$, $C_1$ and $C_2$ such that
    for every $n \ge N$,
    there exists an input $A$ of size $n$
    such that $C_1 n^2 \le T(A) \le C_2 n^2$
            and for all inputs $A'$ of size $n$, $T(A') \le T(A)$.

If you show that quicksort is $O(n^2)$ (i.e. at most $n^2$ for large $n$, up to a scaling factor), that obviously tells you that the worst case is $O(n^2)$, but there may be a better bound. If you want to prove that the worst case is $\Theta(n^2)$, i.e. that quicksort for large enough $n$ is sometimes approximately $C \, n^2$ but never more for some $C$, it's enough to know that quicksort in general is $O(n^2)$ and that there is some input distribution (for every $n$) that's $\Omega(n^2)$, i.e. at least $C_1 n^2$ for large enough $n$.

I am sorting a list of numbers which are in descending order , should't it be a worst case scenario already???

There is no intrinsic relationship between the original order of the elements and the difficulty of sorting them. Sorting numbers that start out in descending order is not intrinsically harder than any other order. With quicksort, what input distribution constitutes the worst case depends on how the pivot is chosen. For example, if you always pick the first element as the pivot, input that is in ascending order and input that is in descending order both reach the $\Theta(n^2)$ worst case. If you always pick the middle element as the pivot, these two input distributions do not reach the worst case — an example worst case would be with the smallest element in the middle (position $\frac{1}{2} n$ rounded to an integer), the next smallest at position $\frac{1}{4} n$, the next at $\frac{3}{4} n$, the next four at $\frac{1}{8} n$, $\frac{3}{8} n$, $\frac{5}{8} n$, $\frac{7}{8} n$, and so on.

Answer 3

To answer your question directly, In the worst case, there will be n-1 comparisons in the first recursion, n-2 comparisons in the second recursion, n-3 comparisons in the third, and so and so on, so actually, with n = 10000, I would expect the number of comparisons to be closer to 50,000,000.

As for the actual code, I think you need an additional datacomparison++ after the while ( container.get(i) < pivot && maxarraybound == false) loop, as well as an additional datacomparison++ after the while ( container.get(j) > pivot) loop. If you think about how while loops work, you will realize that an additional comparison is performed for the while loop to exit, which you are not counting.

I think with the above two changes, you may get something quite close to 50 million comparisons.

Answer 4

here is a writeup for an NYU CS lecture containing info/reasoning on why quicksort is $O(n^2)$ in worst case even with any choice of pivot algorithm, skip to section "Worst case of quicksort". others have pointed out why $O(f(n))$ notation is not really a formula for individual datapoints. as for finding $O(n^2)$ in practice, ie via empirical experiment/ exercise as you seem interested in, try writing code that repeatedly runs Quicksort on worst case inputs (previously sorted ascending or descending) of size $n..m$ and graph the results, and fit it to a function.