1
$\begingroup$

Given a set of points on a plane find the set of $n$ points that are closest to the origin. (Points are pairs of integers.)

  1. Input: list of points.
  2. Initialize a priority queue $Q$, where priority is measured according to the distance from origin (larger distance is higher priority).
  3. For each point $p$:
    • Add $p$ to $Q$.
    • If $Q$ contains $n+1$ points, remove the point with highest priority.
  4. Return $Q$.

The priority queue is implemented using a heap.

I'm thinking the runtime is $O(n + k \log n)$, and space is $O(n + m)$. Where $n$ is the number of points examined, $m$ is the number of points being returned and $k$ is $\max(0, n - m)$. Space is both the priority queue and the output.

My understanding is that a heap can be constructed in $O(n)$ hence the $O(n)$ in the runtime complexity. I find it hard to reason why heap construction, which has an upper bound $O(n \log n)$ can be reduced to $O(n)$, but $k$ deletions should be $O(k \log n)$.

I might be overthinking this, but thought I would ask.

$\endgroup$
1
$\begingroup$

There seems to be some confusion regarding parameters. There is $n$, which is the number of points we wish to return; and there is another parameter, let's say $N$, which is the number of points in the input. Assuming that $N \geq n$, the output would consist of $n$ points, so we can dispense with your $k$.

Since the heap contains at most $n$ points, all operations take $O(\log n)$ time. Therefore the running time can be upper-bounded by $O(N\log n)$. It should be easy to construct matching hard instances which show that the worst-case time complexity is indeed $\Theta(N\log n)$.

Regarding space consumption, the usual convention is to measure only the "work tape", that is, only the auxiliary space taken by the procedure, without the input and output. In this case, this is only the heap, which uses up $\Theta(n)$ space.

$\endgroup$
  • $\begingroup$ The reason I introduce k is to note a diffeence berween the number or points, the number of points returned, and the number of times delete is called (k times). The upper bound on points returned is N, because one cannot return points that were not provided. So worst case we return all but one of the points, and I say all but one because the entire algorithm would need to run in order to determine which point to eliminate whereas if the N is n then just return the original set of points. $\endgroup$ – lucidquiet Jul 26 '18 at 4:08

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.