Do We Need Asymptotic Analysis?

The answer is of course yes². We will use the example of sorting to illustrate what asymptotic analysis can tell us about actual performance of code. While doing this, we will also go through examples of how to write algorithm ideas and details as well as proof ideas and details (which you will need to write in your homework solutions).

Sorting

For this discussion, we can assume that the numbers are all positive integers.
As if you expected a different answer!
The input is on the left and the output on the right. The index of an element is below the corresponding box and the corresponding value is above the box in blue. In the rest of the discussion we will be dealing with a lot more elements and will omit these labels.
No, this is even more brute force than what you might think of.
In your actual homeworks solution you should not leave a "dangling pointer" as in the reference to correctness of nextPerm in the algorithm above. However, it is perfectly OK to leave a reference to an existing result (e.g. something from the book, lectures or any 331 material).
Most of the algorithms that we will consider in this course will have obvious arguments for its termination and we will most times not explicitly argue that the algorithm under consideration terminates. (Note that termination of an algorithm is a necessary condition for it to be correct.) However, the first algorithm we see in this course will have a somewhat non-trivial termination argument.
One might think that we are done here. But we still have to argue that min does not get assigned another non-minimum value in a later iteration.
In all of the induction proofs in the two exercises in this page, we only has one "object" for a given value of the parameter: e.g. n! for integer n. However, in this case we consider all possible arrays B and C that have a total of m+n elements. Note that there are potentially infinitely many such arrays.
Prove this!

We begin our discussion with the classical sorting problem.

Sorting

Input:

$n$ numbers $a_0,\dots,a_{n-1}$ ¹.

Output:

The $n$ numbers in non-decreasing order.

For example, if the input numbers are (for $n=6$): \[9,7,10,20,1,11\] then the output should be \[1,7,9,10,11,20.\] For this discussion, we will illustrate the input as a bar chart where the $i$th column represents the $i$th entry in an array and the height of a column is proportional to the value. For example, we will represent the example input and output above as³

Algorithms

We next dive into algorithms for solving the sorting problem.

Brute Force Algorithm

We begin with the brute force algorithm ³:

Brute Force Algorithm (Idea)

We will cycle through all possible permutations $\pi$ on $\{0,1,\dots,n-1\}$; re-order the numbers as $a_{\pi(0)},a_{\pi(1)},\dots,a_{\pi(n-1)}$ and check if this sequence is the sorted order. If so, we stop else we continue to the next permutation.

Brute Force Algorithm (Details)

				// Input: A[i] for 0<= i<n

				//Initialize the permutation to be the identity
				for(i=0; i< n; i++)
					P[i]=i;  //The array P will store the current permutation

				//Loop till we find the sorted permutation
				while(!isSorted(A,P))
					P=nextPerm(P);

				//Output the sorted numbers
				for(i=0; i< n;i++)
					print(A[P[i]]);


				//The function isSorted
				bool isSorted(A,P)
				{
					flag=true;
					for(i=0; i<n-1 && flag; i++)
						if(A[P[i]] > A[P[i+1]])
							flag=false;

					return flag;
				}

Missing Detail

In the algorithm detail above, we did not specify how we implement the nextPerm(P) function. We will come back to the implementation of this function later on but for now assume that one can have a correct implementation of this function that runs in time $O(n)$. In other words, when nextPerm is called successively, we will assume that it cycles through all possible permutations in some order. (See for more on this.)

Below we present a run of the brute force algorithm (for $n=6$ with random values). The input is on the left and the figure on the right presents the values in A ordered according to the current permutation P. (Click on the "Restart" button if you want to re-run the algorithm on a new random input.)

Correctness

The correctness of the brute force algorithm above should be obvious but we present the idea and details on a proof of correctness of the algorithm to give you guys more examples of how to divide up your solutions into proof ideas and proof details.

Proof Idea

The proof follows from the observations that the sorted output is a permutation $\pi$ of the original set of numbers such that all the number in order according to $\pi$ are non-decreasing. The function isSorted checks if the number according to the current permutation is non-decreasing. Finally, we have assumed⁵ that nextPerm correctly produces all permutations and hence the algorithm above will find the correct $\pi$ eventually.

Proof Details

We begin by arguing that isSorted correctly checks if the numbers ordered according to the permutation stored in P are in their sorting order. If P is not such a permutation then this necessarily implies that there is an index i such that A[P[i]]>A[P[i+1]]. In such a situation the check in line 21 will catch this condition and the function would return false as desired. If P is indeed the permutation corresponding to the sorted order then (by definition of the sorting problem) for every i we have A[P[i]]<= A[P[i+1]] in which case flag is never set to false and hence the function returns true as desired.

We now argue that the overall algorithm is correct: i.e. it outputs the sorted numbers in lines 11 and 12. We first note that is the algorithm considers a permutation P such that A[P[0]],A[P[1]],...,A[P[n-1]] is the sorted order then isSorted when called on this P will return true and hence, the algorithm will reach lines 11-12, as desired. Next, we note that given our assumption on the correctness of nextPerm, the algorithm will ultimately have the correct permutation in P. This follows from our assumption that if nextPerm is called repeatedly it will cycle through all possible permutation and hence at some point the algorithm will have the correct P. Finally, since the number of permutations is finite, the algorithm will terminate⁶.

Runtime Analysis

Next, we do a runtime analysis of the brute force algorithm. This is where (as you have seen in CSE 116 and CSE 250) we will use asymptotic notation. For this article, we will assume that the reader is familiar with the "Big-Oh" notation. (For a refresher, see Section 2.2 in the Kleinberg-Tardos book or use your favorite online resources: e.g. Wikipedia or Khan Academy .)

Factorial Function

As we will see shortly, we will need to work with the factorial function (for a refresher, see the Wikipedia page or the Khan academy video on the factorial function ):

Factorial function

For a positive integer $n\ge 1$, its factorial function, denoted by $n!$ is defined as \[n! = 1\times 2\times \cdots \times n=\prod_{i=1}^n i.\]

The reason why we are interested in the factorial function is that the total number of permutations (i.e. the maximum number of distinct assignments to the array P that the algorithm might have to cycle through) is exactly $n!$. We leave the proof of this claim as an exercise:

Exercise

Prove that the number of distinct permutations of $n$ items is exactly $n!$.

Hint: Use induction on $n$.

Big-Oh Upper bound

We now argue that the brute force algorithm runs in time $O((n+1)!)$. To see this we note that each call to the function isSorted takes $O(n)$ time since the function has a loop that runs at most $n$ and each iteration takes $O(1)$ time. A similar argument shows that lines 4-5 and 12-13 take $O(n)$ time. This implies that algorithms spends $O(n)$ overall in all the lines except for lines 8-10. By the exercise above the algorithm repeats the while loop in lines 8-9 at most $n!$ time and since each call to isSorted and nextPerm takes $O(n)$ time (the former follows by the argument at the start of the paragraph while the latter follows from our assumption on nextPerm). Since $n\cdot n!$ is $O((n+1)!)$, we have that the overall runtime is $O((n+1)!)+O(n)=O((n+1)!)$, as desired. In fact, one can argue that the analysis above is tight in that the brute force algorithm also runs in time $\Omega((n+1)!)$. Note that this implies that for every large enough $n$, there is an input $a_0,\dots,a_{n-1}$ such that given this specific input the algorithm takes $\Omega((n+1)!)$ steps. We leave a proof of this claim as an exercise:

Exercise

Prove that the brute force algorithm has a runtime of $\Omega((n+1)!)$.

Selection Sort

We next consider the well-known selection sort algorithm (see e.g. its Wikipedia page ).

Selection Sort (Algorithm Idea)

The algorithm iteratively computes a partial sorting order. In particular, after iteration $i$, the first $i$ elements will be in their correct sorted order. In the next $(i+1)$th iteration, the algorithm computes a smallest value among the remaining $n-i$ unsorted value and places it in position $(i+1)$.

Selection Sort (Algorithm Details)

				//Input: A[i] for 0<= i<n

				for(i=0; i< n; i++) // At end of iteration i, A[1],..,A[i] will be the correct sorted prefix
				{
					min=i;
					for(j=i+1; j< n; j++) //Find the minimum among the unsorted elements
						if(A[j] < A[min])
							min=j;

					//Swap the smallest value to location i
					temp = A[i];
					A[i] = A[min];
					A[min] = temp;

				}

Below we present a run of Selection Sort (for $n=100$ with random values). The figure presents the values in A at the end of each iteration i. (Click on the "Restart" button if you want to re-run the algorithm on a new random input.)

You might have noticed that a run of Selection sort even with $100$ inputs runs way faster than the brute force algorithm with just $n=6$. We'll do a more direct comparison shortly.

Correctness

The correctness of the selection sort almost immediately follows from the proof idea. However, for illustrative purposes we present both the idea and the details of the proof of correctness.

Proof Idea

We will prove the correctness of the selection sort algorithm with a proof by induction on i. In particular, we will prove by induction that at the end of iteration i, the sub-array A[0],...,A[i] contains the i smallest (among the original $n$) values in their correct sorted order. The inductive step of the proof follows from the correctness of lines 5-8 in computing the minimum among the values A[i],...,A[n-1].

Proof Details

Fix an arbitrary $0\le i\lt n$. We first argue that lines 5-8 correctly compute the smallest value among A[i],...,A[n-1]. More precisely min is indeed the index of the smallest number among the $n-i+1$ values. We prove this claim with a proof by contradiction. For the sake of contradiction, assume that min is not the index of the smallest number among A[i],...,A[n-1]. This implies that there exists a value $i\le j \lt n$ such that A[j]<A[min] and j indexes the true minimum value (or one of them if there are multiple smallest values). However, in this case when line 7 is executed for this value of j then in line 8 we do the assignment min=j.⁷ If this was the last iteration when min is modified then we are done. To complete the argument assume that min is modified at a later iteration $j'$. However, by the condition in line 7, this implies that A[j']<A[min]=A[j], which contradicts the assumption that j indexes a minimum value.

We now finish the proof by induction. We claim that at the end of round $i$, A[1],...,A[i] is the sorted order of the $i$ smallest values: i.e. we have that A[j] <= A[j+1] for every $0\le j\lt i$ and A[l]>=A[i] for every $l\gt i$. For the case base of $i=0$, the argument in the paragraph above implies that after the $0$ iteration, A[0] will contain the smallest number. For the inductive hypothesis assume that for every $i\ge 0$, A[1],...,A[i] is the sorted order of the $i$ smallest values. Then we claim that after the end of the $(i+1)$th iteration A[i+1] is the $(i+1)$th smallest value among the original $n$ values. Note that this will prove the inductive step. Finally, the proof of the claim follows from lines 5-8 and the correctness argument in the previous paragraph.

Runtime Analysis

The runtime analysis of the selection sort algorithm is fairly straight forward. The outer for loop runs for at most $n$ times and in each iteration lines 5-8 find a minimum value and lines 11-13 swap two elements, The latter takes $O(1)$ time while the former takes $O(n)$ time. Indeed the for loop on line 6 is repeated at most $n$ times and each repetition takes $O(1)$ time. Thus, overall the outer for loop runs at most $n$ time and each such iteration takes $O(n)$ time, which leads to an overall $O(n^2)$ time.

An Aside

You might have noticed that we were a bit sloppy in our analysis of selection sort. We take a very brief detour to point out that we were not sloppy at all (at least asymptotically). Note that we were sloppy in our accounting of how much time the algorithm spends on computing the min values so we only concentrate on how many times line 7 is repeated. Note that when the outer for loop is at value $i$, then the inner for in line 6 is repeated exactly $n-i-1$ times. Thus the total number of times line 7 is repeated is exactly \[\sum_{i=0}^{n-1} n-i-1 = n^2 -\sum_{i=0}^n i -n = n^2 -\frac{n(n-1)}{2}-n=\frac{n^2-n}{2}.\] In the above we used the following identity (in our case $m=n-1$ and note that $\sum_{i=0}^{n-1} i =\sum_{i=1}^{n-1} i$ since $i=0$ does not contribute to the sum), the proof of which we leave as an exercise

Exercise

Show that for every integer $m\ge 1$, \[\sum_{i=1}^m i = \frac{m(m+1)}{2}.\]

Hint: Use induction on $m$.

Finally, note that $\frac{n^2-n}{2}$ is asymptotically equivalent to $n^2$ (or in other words it is $\Theta(n^2)$) and hence our "sloppy" bound of $O(n^2)$ above was indeed correct.

Comparing With the Brute Force Algorithm

So far we have seen that the brute force algorithm takes $O((n+1)!)$ time while selection sort takes $O(n^2)$ time. It can be verified that the latter is asymptotically a smaller run time:

Exercise

Argue that $n^2$ is $O((n+1)!)$.

In fact, it can be shown that $(n+1)!$ factorial is waaaay bigger than $n^2$: in particular, the former is worse than exponential time while the latter is polynomial time. (To argue this formally use the Striling's approximation .) Thus, asymptotic analysis tells us that Selection sort should run (much) faster than the brute force algorithm. This is indeed the case. E.g. consider the following runs of the selection sort and brute force algorithm on $n=100$ random inputs (click on the "Restart" button if you want to re-run the algorithms on a new random input):

Tip

Do not wait for the brute force algorithm to finish. Even if you keep it running non-stop it won't finish before you graduate from UB (and then some).

Mergesort Algorithm

Finally, we present the well-known Merge sort algorithm (see e.g. its Wikipedia page ).

Merge sort (Algorithm Idea)

For simplicity, let us assume that $n$ is a power of $2$, i.e. $n=2^s$ for some integer $s\ge 1$. The algorithm will run in $s$ iteration. In iteration $i$ (for $1\le i\lt s$), we will ensure that at the start of iteration $i$ all consecutive chunks of $2^i$ elements are sorted (this is the pre-condition for iteration $i$). Then in the meat of iteration $i$, we will look at two consecutive chunks of size $2^i$ (recall both of them are sorted) and combine them into one sorted chunk of size $2^{i+1}$. Note that this implies that the precondition for iteration $i+1$ is satisfied. Note that at the end of the last iteration $i=s-1$, we will have one chunk of $2^s=n$ sorted numbers, which will be our output.

Merge sort (Algorithm Details)

			//Input A[i] for 0<= i < n
			//Assume n=2^s for integer s>=0

			for( i=0; i< s; i++)
			{
				//At start of iteration i all chunks of 2^i consecutive elements are sorted
				for( j=0; j< n/i; j+=2) // Consider all pairs of consecutive chunks of size 2^i
				{
					B = A[j*2^i, (j+1)*2^i-1]; // A[l,r] is shorthand for the subarray A[l], A[l+1],...,A[r]
					C = A[(j+1)*2^i, (j+1)*2^i-1];

					A[j*2^i, (j+2)*2^i-1] = Merge(B,2^i,C,2^i); // Update the relevant chunk of size 2^{i+1}
				}
			}

			int [] Merge (B, m, C, n) 
			//Combine two sorted arrays (B of size m and C of size n) into one sorted array of size m+n
			{
				int D = new int[m+n]; // Initialize the array to be returned

				i=j=k=0;

				while (i< m and j< n) // Repeat while neither B nor C has been exhausted
				{
					if(B[i]<C[j])
						D[k++] = B[i++];
					else
						D[k++] = C[j++];
				}

				while (i< m) //B has not been exhausted
					D[k++]=B[i++];
				while (j< n) //C has not been exhausted
					D[k++]=C[j++];

				return D;
			}

Recursive vs. Iterative

The "usual" statement of the Mergesort algorithm is a recursive one while the Mergesort algorithm above is an iterative one. Recursive algorithms are theoretically more elegant and generally allow for cleaner proofs of correctness. However, in practice if possible one should always codeup iterative versions of a recursive algorithm. Recursive algorithm have an overhead because in practice we have to pay for the call stack that the program will have to use. Typically, iterative implementations can avoid this overhead. In CSE 331, we will explicitly convert recursive algorithms into iterative ones when we consider dynamic programming algorithms.

Below is a run of the Merge sort algorithm with $n=400$ random values. The figure represents the values in A at the end of each iteration i (in the for loop in line 4). (Click on the "Restart" button if you want to re-run the algorithm on a new random input.)

Correctness

The heart of the Mergesort algorithm is the Merge routine so we start with the correctness of this sub-routine.

Correctness of `Merge`

Recall that we have show that on input B with m elements in sorted order and C with n sorted elements, Merge returns the union of the m+n elements in sorted order (or equivalently the array D returned in line 36 has the elements of B and C in sorted order). We will prove this by induction. Since this proof might be of a slightly different kind of induction proofs you might have seen in CSE 191, we next present the proof.

Proof Idea

We will prove the correctness of Merge with a proof by induction on $m+n$. In particular, for the inductive hypothesis we will assume that for every pair of arrays B and C such that the total number of elements in B and C is $m+n$, Merge returns the union of all the elements in B and C in sorted order.⁸ The proof of the inductive step follows from considering the steps of the Merge sub-routine.

Proof Details

We will induct on $m+n$. In particular, our induction hypothesis is as follows: for every integer $t\ge 2$ the following is true for every pair of positive integers $(m,n)$ such that $m+n=t$. For every possible (non-empty) arrays B (with $m$ elements) and C (with $n$ elements), Merge(B,m,C,n) returns an array D (with $m+n$ elements) that has the elements of B and C in sorted order.

We begin with the base case $t=2$. Since B and C are non-empty this implies that $m=n=1$. We consider the case B[0]<C[0]. In this case in line 26, we will have D[0]=B[0] and in line 34, we will have D[1]=C[0], which is the correct sorted order. Similar arguments handle the case of B[0]>=C[0]. This completes the proof of the base case.

We now present the inductive step. Assume that the induction hypothesis is true for all pairs of arrays (B',C') with size pairs $(m',n')$ such that $m'+n'=t$. Now consider an arbitrary pairs of arrays (B,C) with sizes $(m,n)$ such that $m+n=t+1$. We complete the proof by a case analysis:

B[0]<C[0]. On line 26, Merge will do the assignment D[0]=B[0]. (This is the correct assignment since B[0] is the smallest element in the union of B and C.⁹) If $m=1$, then Merge will assign all the elements of C to D[1,t] in lines 33-34. (Note that in this case B followed by C is the correct sorted order, which is what D will contain.) If $m>1$, then let B'=B[1,m-1] and C'=C. Further, the rest of the execution of Merge is the same as assigning Merge(B',m-1,C',n) to D[1,t]. By the inductive hypothesis (since $m'+n=m+n-1=t$), this implies that D[1,t] has the elements of B' and C' in sorted order. Since B[0] is the smaller than all elements in B' and C', this implies that D will have all the elements of B and C in sorted order.
C[0]<=B[0]. The argument is same as in the previous case (where we swap the roles of B and C).

Since our choice of B and C was arbitrary (subject to the condition $m+n=t+1$), the above argument proves the inductive hypothesis for every array B and C with $m+n=t+1$, which completes the proof.

Rest of the Argument

The correctness of the Mergesort algorithm follows from the correctness of Merge and induction, which we leave as an exercise.

Exercise

Prove that the Mergesort algorithm is correct.

Hint: Use induction on the index of iteration i in the for loop on line 4.

Runtime analysis

We first need to do the runtime analysis for the Merge, which is left as an exercise:

Exercise

Argue that Merge runs in time $O(m+n)$.

Given the above, it is easy to argue that each iteration of the for loop on line 4 runs in time $O(n)$, which implies an overall runtime of $O(n\log{n})$. The proof is left as an exercise:

Exercise

Argue that Mergesort algorithm runs in time $O(n\log{n})$.

It can be shown that $n\log{n}$ is aysmptotically smaller:

Exercise

Argue that $n\log{n}$ is $O(n^2)$.

Thus, asymptotic analysis says that Mergesort will run faster than Selection sort (and in turn way faster than the burte force algorithm). This is indeed the case. Consider e.g., the following runs of the three algorithms on $n=400$ random inputs (click on the "Restart" button if you want to re-run the algorithms on a new random input):

Do We Need Asymptotic Analysis?

Sorting

Sorting

Input:

Output:

Algorithms

Brute Force Algorithm

Brute Force Algorithm (Idea)

Brute Force Algorithm (Details)

Missing Detail

Correctness

Proof Idea

Proof Details

Runtime Analysis

Factorial Function

Factorial function

Exercise

Big-Oh Upper bound

Exercise

Selection Sort

Selection Sort (Algorithm Idea)

Selection Sort (Algorithm Details)

Correctness

Proof Idea

Proof Details

Runtime Analysis

An Aside

Exercise

Comparing With the Brute Force Algorithm

Exercise

Tip

Mergesort Algorithm

Merge sort (Algorithm Idea)

Merge sort (Algorithm Details)

Recursive vs. Iterative

Correctness

Correctness of Merge

Proof Idea

Proof Details

Rest of the Argument

Exercise

Runtime analysis

Exercise

Exercise

Exercise

Further Reading

Correctness of `Merge`