Running time of median of 3 partioning 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:


Median of Medians Recurrence Relation for 3-grouping
Counting elements that are greater than the median of medians
http://www.cs.fsu.edu/~breno/COP-4530/slides/21-anim.pdf
You should not confuse median-of-median algorithm with median-of-3 trick.

The former is $O(n{\rm log}n)$ worst-case time.

Ans. to 1. The latter is still $O(n^2)$ worst-case time but faster in practice due to the low frequency of bad patterns seen in practice. This can be seen by the fact that randomized quicksort is $O(n{\rm log}n)$ expected time.

Ans. to 2. It is $O(n)$. The comparison work is $O(1)$ since there are only $3$ elements involving. After, determine the value of the median of three, you need to partition the array around this value. This takes $O(n)$ time.