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

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())
{
}

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?

• By $O(n^2)$, you cannot conclude that the number of primitive operations are $n^2$. – preetsaimutneja Aug 15 '14 at 6:35
• @sai_preet why cant i ??? I am sorting a list of numbers which are in descending order , should't it be a worst case scenario already??? – Computernerd Aug 15 '14 at 6:53
• This question has a couple of problems. 1) Please get rid of the overly specific Java code; pseudocode should be sufficient for discussing your problem and is much more approachable. 2) You seem to be confused about basics in algorithm analysis. One has been address by sai_preet, another is that the number of elements you have is irrelevant, as are the concrete numbers. In fact, you don't do anything that resembles algorithm analysis. I recommend you check out our reference questions. – Raphael Aug 15 '14 at 7:41
• If you want to analyze this the best way to do it is mathematically.. I am guessing you know the big-oh notation, so why not write a pseudo-code and just think what can be the the worst.. however if you are randomizing it, chances are it will be extremely difficult to ever 'see' the worst. Also, never use empirical results to analyze algorithms.. for one thing, you may not ever encounter the "worst-case".. quicktime (on the avg case is known to run in $O(nlog)$ time.. Also if you must do something like this, remember the big-oh hides a LOT OF CONSTANTS, so again, analyze mathematically without – Subhayan Aug 15 '14 at 7:46
• strange this nearly same question has 25v on stackexchange. see also math.se. the answer seems to come down to the pivot algorithm; naive algorithms eg no pivot logic perform more poorly. not sure if the median-of-3 algorithm still has $O(n^2)$ worst case. the question seems quite reasonable to me in the sense of "construct the worst case input & prove it takes $O(n^2)$", not sure why the opposition. – vzn Aug 15 '14 at 14:52

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!

• Ad first part: the "doubling test/method" (as Sedgewick calls it) is indeed useful for estimating asymptotic runtime up to $\Theta$; you get good guesses if you samples are large enough. It's noteworthy that the proposed calculation works even if you add in the constant factors! Ad part 2: good points all, but if that's what the question boils down to, it's a duplicate of our reference question. – Raphael Aug 15 '14 at 20:43

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.

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.

• "In the worst case, there will be n-1 comparisons in the first recursion..." -- and the proof of that is what's to do. – Raphael Aug 16 '14 at 9:27
• @wookie919 I am sorry but i dont understand the part where i require an "additional data comparison" to exit for while loops – Computernerd Aug 24 '14 at 0:23
• @wookie919 how about the "while (i<=j) " part – Computernerd Aug 24 '14 at 0:51
• @Computernerd i and j are indices. You need to distinguish between index comparisons and data comparisons. Consider the code i = 0; while (i < 9) {i++;}. At the end of the while loop, i will be 9, but 10 comparisons have been performed. – wookie919 Aug 24 '14 at 3:45

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.

• see also quicksort analysis incl recurrence relation for worst case – vzn Aug 24 '14 at 15:18
• here is another nice emprical analysis by marceau, see the figures graphing the quadratic worst case performance starting p7. – vzn Aug 24 '14 at 15:22
• yet another analysis – vzn Aug 24 '14 at 15:34
• No decent implementation of Quicksort has worst case behaviour for previously sorted arrays. Since sorting sorted arrays is in practice so common, these cases often run in linear time with a good implementation. – gnasher729 Feb 5 at 0:00