I am hoping someone can break something down for me in a way I can digest. I am trying to understand the running time for the median of three partitioning.
What is the goal of median of three partitioning? Is it to eliminate the possibility of selecting the largest / smallest element as the pivot, thus resulting in O(n^2) run time?
What would the run time be of a simple median of three partitioning function? Since there are only 3 possible comparisons, and the comparison operation runs in O(1) time, wouldn't it just be 3O(1) or negligible?
Any assistance would be greatly appreciated. Thus far, I have referenced CLRS and the following three pages for assistance: