Originally posted on Jul 15, 2014
We had discussions about starting off with the topic of algorithms and discussing about mathematical background for the same.
We had planned in discussing about characteristic equation.
Its the mathematical representation of a problem. Generally we may encounter (almost all the time) a problem that
needs to re-iterate over n times or it has a sample set of size n to be subjected to the same operation. In order to encompass all the process
in one equation i.e., in order to recurrse the problem through the entire sample set we need to frame equations called recurrence equations.
If I sound a little confusing then I’m sorry they both ARE the same.
Let us take a problem to analyze and write down the recurrence equation for the same.
I’m sure almost everybody in the field of computer science must have heard about sorting and one of the most of commonly used solution for it is quick sort. (If not check out the wiki page of quicksort for a quick introduction.) The problem involves in sorting a list of numbers (say) ‘n’ in either ascending/descending order.
The algorithm goes something like this,
-
We initially choose a random pivot element and divide the list of numbers in two halves based on the pivot element. Here a pivot element is the number of demarcation dividing the list of numbers into two.
- This number could be any number in the list (this argument warrants a seperate discussion, problem of choosing a pivot element, so we shall deal it in the subsequent journals).
- This division is the process of segregating all those numbers greater than the pivot element, to the right sublist and all those elements less than the pivot element to the left sublist (if we are soring in ascending order. The reverse holds good for descending order).
-
Once the list is divided into two halves we do step-1 for left sublist and right sub-list.
- This means we now consider the left sublist and again choose a random pivot element and then again start to divide the sublist into two further sublists.
- The same applies for the right sublist too.
-
Recurrse the process until the list becomes a single element (each newly formed sublists).
An example of the process of dividing the list and sorting is shown in the follwin diagram,
Ok now to the mathematical part. Let us denote the time taken by the algorithm to sort the numbers to be ‘T(N)’.
During the first step once the pivot element is chosen the list is divided into two halves. Right sub list and the left sub list.
The algorithm says “Once the list is divided into two we do step-1 on left and right sublists” i.e., we sort left and right sublists by quicksort. i.e., choose a pivot element in the left sublist and inturn divide it into two halves. i.e., apply quick sort to left sublist.
The time taken for this operation will be T(N/2) (based on previous assumption of T(N) to sort N items).
So the equation roughly forms like,
T(N) = T(N/2) + T(N/2) + some more time(for comparison operation to divide the list).
The some more time is the time taken for making comparisons for arraging the list as right sublist and left sublist.
Exactly we will be making (N-1) comparisons for making partitions.
This equation is the recurrence equation that we need to derive for getting the running time.
But this equation is of no use without eliminating the function from the right-hand side. One cannot express time as a function of time to calculate time !! We solve the recurrence equation to derive an equation as a function of N(input).
I hope I gave a brief introduction about approaching a problem. I am not going to solve the recurrence equation in this journal as it requires much more basics to brush up. I leave the rest of the problem for the next one!