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

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)$$.

• You should show your ideas/solution tentative and ask for more specific help. Furthermore, you can improve your question cs.stackexchange.com/help/how-to-ask Commented Dec 12, 2023 at 15:23
• Answer is O(N^2logN) Commented Dec 12, 2023 at 16:04
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)$$.
• Additionally, if there are more than $256$ possible values, we may use quick select instead in $O(n^2)$ time. Commented Dec 12, 2023 at 19:59