Tutorial #8 solutions – CPSC 320 2017W2

Algorithm UndominatedPoints(P, q)
  S ← { }
  for each point p of P do
    if q.x < p.x or q.y < p.y then
      add p to S
  return S

Algorithm MaximalPoints(P)
  sort P by increasing x-coordinate
  return MaximalPointsHelper(P, 0, length[P]-1)

Algorithm MaximalPointsHelper(P, first, last)
  if first = last then
    return { P[first] }

  mid ← ⌊(first + last)/2⌋
  Sl ← MaximalPointsHelper(P, first, mid)
  Sr ← MaximalPointsHelper(P, mid+1, last)

  q ← point of Sr with largest y-coordinate
  return Sr ∪ UndominatedPoints(Sl, q)

Let H(n) denote the running time of MaximalPointsHelper when it is called with a portion of P that contains n elements. Finding the point of Sr with largest y-coordinate and the call to UndominatedPoints takes O(n) time, and so H(n) satisfies the recurrence: H(n) = H(⌈ n/2⌉) + H(⌊n/2⌋) + Θ(n) if n ≥ 2 with H(1) ∈ Θ(1). By case 2 of the Master theorem, H(n) ∈ Θ(n log n). The sorting step of algorithm MaximalPoints can also be done in Θ(n log n) time, using MergeSort, and so algorithm MaximalPoints runs in Θ(n log n) time.

We use a recursion tree. We have drawn the first three levels of the tree. The blue text denotes the work done at each node (not all of these are written for the nodes on the third level, as that much text would have been very hard to read). The red text is the sum of the work at each level of the tree.

The root does 2n² work. The sum of the work on level 2 is 2(4n/5)² + 2(2n/5)² + 2(n/5)² = 2n². The sum of the work on level 3 is similarly 2n².

The first leaf of the tree occurs at level log₅ n. Because the first log₅n levels of the tree all do 2n² work, we thus get a lower bound of 2n²log₅n on T(n). The last leaf of the tree is at level log_5/4n, and hence T(n) ≤ 2n²log_5/4 n. Since log_5/4n = log₅n / log₅ (5/4) , this means that T(n) ∈ Θ(n²log n).