Originally posted on Jul 16, 2014
Its about the characteristics/recurrence (although these two equations are subtly different in mathematical basis they are interchangeable. I know I am contradicting myself with my previous journal but this is just a trivial message that we need to remember about recurrence equations) equations that we derived for the problem of quick sort and we wanted to reduce the equation such that its just a function of the input i.e., to eliminate the time function from the right side of the equation.
There are three ways in solving a recurrence equation.
1.Using Induction.
2.Using algebraic method of solving the characteristics equation.
3.Using Substituition.I shall solve the the recurrence equation for quick sort in all the three methods.
The method of induction is more of an analysis method rather than a deductive method in analysing and solving a recurrence equation. It ofcourse can be used in solving a recurrence equation but it is more of an analyzing method rather than a deduction method.
Anyways this was the recurrence equation that we got after our analysis in the previous post.
T(N) = 2*T(N/2) + N-1
the method of induction follows the normal procedure…
T(1) = 0 , Since with just single element you don’t have anything to sort.
T(2) = 1 (2* T(1) + 2-1) , with just two elements we just need one single operation to sort. Obvious! .
T(3) = 2 (2* T(3/2) + 3-1), this could also be done in one single operation but let us go by the book. That is the best case for the algorithm.
T(4) = 5 (2* T(4/2) + 4-1),
T(8) = 17 (2* T(8/2) + 8-1),
T(16)= 49 (2* T(16/2) + 16-1),
..
...
....
Ok this is where this method gets quite tough for use. Now with this pattern of equations and their solutions to initial values we need to identify the pattern that might be generated for this particular equation.
Ok let us see. Hhhhmmm we have 0,1,2,5,17,49,….
N=1: Ok 0 is not a power of 2 nor a perfect square… ( I am just trying to find a familiar and easily solvable pattern. You can approach this problem in anyway)
N=2: 1 is not .. (1-0)
N=3: 2,
N=4: 5 is not.. (8-3) ,
N=8: 17 is not ..(24-7),
N=16: 50 is not…. (64-15),
...
....
.....
So what is this 1,8,24,64 corresponding to 2,4,8,16?? Ofcourse we could infer the latter part being (N-1).
You cannot term it as twice. because it doesn’t hold for 8 nor for 16. Thrice??? absurd.
OK well it increases but not drastically. And the constrain is its not a constant and has to be a function associating N.
OK let us try N first i.e., N* N?? Doesn’t hold. ‘log(N)’ ???
Let us try putting log(N) in the equation
Substituting T(N) = N* log(N) – (N-1),
N=2: 2*log(2) -1 = 1,
N=4: 4*log(4) – 3 = 4*2 -3 = 5,
N=8: 8*log(8) – 8-1 = 8*3 – 7 = 17,!!!
N=16: 16*log(16) – 16-1 = 16*4 – 15 = 64-15 = 50!!
Well itseems to hold it… But we just tried for like 4 values and obviously its not going to be feasible for trying it out for inifinitely large numbers.
So we now resort to induction in defending our equation and proving the validity of the same.
T(N) = N*log(N) – N-1 —-A
T(N) = 2*T(N/2) + N-1 —-B
We take the value of N=2 for the basis step since 1 does not hold any meaning with this equation.
T(2) = 2*log(2) + 2-1
= 2*1 + 2-1
= 1.
Which is true if we have just two numbers to sort.
We assume that the equation holds true for some value of K where K being integer and 2<K<N)
i.e., T(K) = K*log(K) – K-1 , holds true for some K
To Prove: T(2k) holds true.
i.e., T(2K) = 2*log(2K) – (2K -1) is true for some 2K < N
We know from equation B that,
T(2K) = 2*T(2K/2) + 2K -1
= 2*T(K) + 2K-1
= 2*[K*log(K) - (K-1)] + 2k-1
= 2K*log(K) – 2*(K-1) + 2k-1
= 2K*log(K) – 2K + 2 + 2k -1
= 2K*log(K) + 1
= 2K [ log(2K) - 1 ] + 1 , algebra = log(K) –> add and subtract by 2
= log(K) + log(2) – log(2)
= log(2K) – 1
= 2K* log(2K) – 2K + 1
= 2K* log(2K) – (2K -1)
Viola! our equation is indeed correct!!
We initially solved the recurrence equation for quicksort for 1,2,3… and so on. We found a pattern in which the solution was obtained. We then guessed a solution to the recurrence equation We then used induciton to prove our claim.
Well actually its just an auxillary tool to help us solve the recurrence eqaution for the algorithm.
Induction method helps us in verifying the result that we obtained and prooving our claim to be valid mathematically.
We have so far covered the first method of the three methods of solving a recurrence equation for an algorithm.
Since the algebraic method of solving an equation demands an extra attention I reserve that for discussion in the next journal.
We shall discuss about the substituition method for now
In the last method we substituted values and started off with the method, but the real substituition is substituiting functions.
Sounds confusing? Well let us look into it.
We already know from the previous discussion,
T(N) = T(N/2) + (N-1) where N is an integer.
This method is just the opposite of the one previously discussed, where we will start to substitute for decreasing values of N.
So now we substitute and derive something like this,
T(N) = 2*T(N/2) + (N-1)
= 2*[2*T(N/4)+ ((N/2)-1)] + N-1 — Since T(N/2) = 2*T(N/4) + (N/2)-1
= 4*T(N/4) + 2*(N/2) – 2 + N -1
= 4*T(N/4) + 2N – 3
= 4*[2*T(N/8) + ((N/4)-1) ] + 2N-3 — Substituiting for T(N/4)
= 8*T(N/8) + N – 4 + 2N – 3
= 8*T(N/8) + 3N -7
= 8*[2*T(N/16) + ((N/8) -1)] + 3N -7 — Subtituiting for T(N/8)
= 16*T(N/16) + N – 8 + 3N -7
= 16*T(N/16) + 4N – 15
= 16*[2*T(N/32) + ((N/16)-1)] + 4N – 15
= 32*T(N/32) + N – 16 + 4N -15
= 32*T(N/32) + 5N -31
..
...
....
and so on it goes,
= n*T(N/n) + N*log(n) – (n-1)
This is the part where we generalize and try to derive the solution to the recurrence equation.
when n=N,
= N*T(N/N) + N* log(N) – (N-1)
= 0 + N*log(N) – N + 1
= N*log(N) – N + 1
Viola!!
A solution to the recurrence equation for quicksort.
Trivia:
If you search for the running time of quicksort you will end up any website showing it as O(nlog(n)). The Big-O notation is another very huge and the most important concept that we need to discuss when dealing with algorithm. After this short stint of mathematics we will get into the asymptotic notations of the running times of algorithm.