I want to calculate the median of running sequence in less than O(n). better if in python. Thanks.
If you want to find real median, there is no way to do it faster than in O(n) (in unstructured array) - because you have to go through all numbers. You never know if the last number you find will be median or not.
For some alghoritms there is heuristic used for finding median, which means you dont get exact median, but you have some approach how to get (with some probability) close to the real one.
For example quicksort requires some median value, but going through whole array would increase average complexity to O(n^2) (and the reason to use quicksort is that it has average complexity of O(n*log n). In such case, you can for example choose 10 random numbers and count the median for them. Then you can say that real median will be probably about this value.