# Computational complexity of calculating mean vs median?

Suppose we have a list $$L$$ consisting of $$N$$ numbers (may include repetitions).

I am curious which is more computationally intensive to calculate, the mean or the median?

Naively, I would suppose calculating the mean involves summing up the $$N$$ numbers and then dividing by $$N$$, hence it has linear $$O(N)$$ complexity.

Computing the median would need to perform some sort of sorting algorithm, https://en.wikipedia.org/wiki/Sorting_algorithm, it seems the best algorithm performs at $$O(n\log n)$$ complexity.

Hence, for general $$N$$, it is more computationally intensive to calculate median? Is my reasoning correct?

Thanks for any help.