2
$\begingroup$

I have an unsorted array of (x,y) coordinates and need to find the min/max for both (x) and (y) separately so that I can build a bounding box using $O(\frac{3n}{2})$ comparisons.

If I use this method to find the min/max for the left/fight box boundaries, then use the same algorithm to find min/max of y for the top/bottom boundaries, does this double the amount of comparisons or can I still claim it’s $O(\frac{3n}{2})$?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ "I sort the array first by the x-coordinates", which implies you have used $\Theta(n\log n)$ comparisons. You just do not do that step. Please update your question accordingly. $\endgroup$ – John L. Nov 28 '18 at 3:50
  • $\begingroup$ @Apass.Jack thanks for pointing that out $\endgroup$ – adamcasey Nov 28 '18 at 3:54
  • $\begingroup$ Please don't destroy/replace the content of your question. Part of our mission is to build up questions and answers that will be useful not only to you but hopefully to others in the future as well. Thank you! $\endgroup$ – D.W.♦ Dec 4 '18 at 4:37
  • $\begingroup$ (My spelling checker doesn't flag left / fight.) $\endgroup$ – greybeard Dec 4 '18 at 8:00
1
$\begingroup$

does this double the amount of comparisons or can I still claim it’s $O(3n/2)$?

You misunderstand the big $O$ notation.

Even if you double or quadruple the amount of comparisons, you can still claim it is $O(3n/2)$. That is, the amount of comparisons as a function of $n$ is asymptotically not bigger than $3n/2$. The very purpose of big $O$ notation is to hide a constant factor so that it becomes clearer what is the asymptotic picture. In fact, $O(3n/2)$ = $O(n)$. When I write "=", I mean equality. That is, the left hand side and the right hand side represent exactly the same set of functions.

Here is what you could say.

If I use this method to find the min/max for the left/right box boundaries and then use the same algorithm to find min/max of y for the top/bottom boundaries, I will use $2(\lceil 3n / 2\rceil - 2) \le 3n -3$ comparisons. That is, I will use $O(n)$ comparisons.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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