$N \times N$ Image Processing Time Complexity: Grayscale to Binary using Median Step Function

Question

In an image processing system, an algorithm processes an $N \times N$ image with each pixel being a number between $0$ and $255$. It finds the median value $M$ in the $N \times N$ image and applies the binary function $f(x)$ to every pixel.

$f(x) = \begin{cases} 1 & \text{if $x ≥ M$} \\ 0 & \text{if $x < M$} \end{cases}$

What is the time complexity of the algorithm? Is it $O(N^2)$ or $O(N^2\ log\ N)$? I think the answer is $O(N^2\ log\ N)$.

Answer 1

It is $O(n^2)$.

Since there are only $256$ possible values, we can use counting sort, a non-comparison sorting algorithm, to count how often each pixel value occurs in $O(n^2)$ time and find the median in $O(1)$ time with at most $256$ steps. Then we can apply the function to each of the $n^2$ pixels in $O(n^2)$.