-2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – SilvioM
    Commented Dec 12, 2023 at 15:23
  • $\begingroup$ Answer is O(N^2logN) $\endgroup$
    – Qammy
    Commented Dec 12, 2023 at 16:04
  • $\begingroup$ You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Commented Dec 12, 2023 at 18:03

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Additionally, if there are more than $256$ possible values, we may use quick select instead in $O(n^2)$ time. $\endgroup$ Commented Dec 12, 2023 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.