The median is one of the most important holistic measures in data analysis. Propose several methods for median approximation.
Analyze their respective complexity under different parameter settings and decide to what extent the real value can be approximated. Moreover, suggest a heuristic strategy to balance between accuracy and complexity and then apply it to all methods you have given.