QuickSort & Master Theorem

QUICKSORT:

Pick pivot. All left of pivot should be less than the pivot, same for the right.

Partitioning can be done in O(n) time.
Reduces problem size. Doesn't need extra memory.

• Choose pivot element.
• Rearrange such that everything left of it is smaller.

PARTITION SUBROUTINE:

If not element, chose another element and swap with the first element for the pivot.

Divide into two- what we have seen and what we haven't seen. First part will be partitioned the right way. ie: Everything smaller than the pivot will be left of the pivot.

j - Boundary point between what we have seen and what we haven't.
i - Boundary between less than pivot and more than pivot. Hence, it points to the last element smaller than pivot.

QUICKSORT (Array, N){
if n=1 return;
P = choose_Pivot(A,n);
Partition A around p;
Recursively call first part;
Recursively call second part.
}

Running time depends on how well the pivot element is chosen. 

NOTE: If a sorted array is passed to QuickSort, the running time will be O(N^2).

For every array size n for QuickSort, the average running time will be O(NlogN).

Best case would be to choose the median everytime, but a 25-75 split is good enough to get O(nlogn) time.  

-----------------------------------------------------------

MASTER THEOREM:

Recursive Algo:
Base case, Work done in recursive call, work done outside the recursive call.

Assumptions :

All subproblems have the same size.
n is a power of b.

 

Master Format: T(N) <= aT(N/b) + O(N^d) or T(N) <= aT(N/b) + cN^d.

• a-> No of recursive calls. or RATE OF SUBPROBLEM PROLIFERATION (RSP). (Evil)
• b-> input size shrinkage factor 
• d->Exponent of work done outside recursive calls.
• b^d -> RATE OF WORK SHRINKAGE (RWS). (Good)

T(N) <= cN^d[a/b^d]^j. (Use merge sort to come to this conclusion) ie:Total work <= cn^d(Work outside recursion) * (sigma from 0 to logba)(a/b^d)^j.

• RSP = RWS : Same amount of work done at each level. Like merge sort. Hence, expect O(nlogn).(Because in the equation, a/b^d =1)
• RSP < RWS: Less and less work with every level. Hence, max work is done at root. Hence, we consider only root time as it will dominate over the rest. Expect O(n^d).
• RSP > RWS: More work done with each level. hence, max work is at leaves. Then leaves time will dominate. Hence, consider only that. Depth of leaves will be O(log(base b)N).

a^(log(base b)N) = No of leaves in a recursion tree.