Computational complexity of calculating mean vs median?
You can find the median in linear time using the linear time selection algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest.

The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.