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.